# Efficient Controllable Multi-Task Architectures

Abhishek Aich⋆,†, Samuel Schulter†, Amit K. Roy-Chowdhury⋆,
Manmohan Chandraker†,‡, Yumin Suh†
⋆University of California, Riverside, †NEC Labs America, ‡University of
California, San Diego

###### Abstract

We aim to train a multi-task model such that users can adjust the desired
compute budget and relative importance of task performances after deployment,
without retraining. This enables optimizing performance for dynamically
varying user needs, without heavy computational overhead to train and save
models for various scenarios. To this end, we propose a multi-task model
consisting of a shared encoder and task-specific decoders where both encoder
and decoder channel widths are slimmable. Our key idea is to control the task
importance by varying the capacities of task-specific decoders, while
controlling the total computational cost by jointly adjusting the encoder
capacity. This improves overall accuracy by allowing a stronger encoder for a
given budget, increases control over computational cost, and delivers high-
quality slimmed sub-architectures based on user’s constraints. Our training
strategy involves a novel ‘Configuration-Invariant Knowledge Distillation’
loss that enforces backbone representations to be invariant under different
runtime width configurations to enhance accuracy. Further, we present a simple
but effective search algorithm that translates user constraints to runtime
width configurations of both the shared encoder and task decoders, for
sampling the sub-architectures. The key rule for the search algorithm is to
provide a larger computational budget to the higher preferred task decoder,
while searching a shared encoder configuration that enhances the overall MTL
performance. Various experiments on three multi-task benchmarks
(PASCALContext, NYUDv2, and CIFAR100-MTL) with diverse backbone architectures
demonstrate the advantage of our approach. For example, our method shows a
higher controllability by $\sim$ 33.5% in the NYUD-v2 dataset over prior
methods, while incurring much less compute cost.

##  1 Introduction

Multi-task learning (MTL) often aims to solve multiple related tasks together
using a single neural network for economy of deployment [1, 2]. Humans can
handle multiple tasks with diverse trade-offs (e.g., due to availability of
resources, adaptable reaction time, etc.), however, most existing MTL
architectures are incapable of transforming themselves to handle multiple user
constraints without being retrained for each scenario. In this paper, we
address the problem of designing controllable dynamic convolutional neural
networks (CNN) for MTL that can adjust jointly for two types of user
requirements, task preference and compute budget.

Figure 1: Problem Setup. We aim to provide users precise control on compute
allocation as per their MTL performance preference, with the ability to change
these dynamically without re-training. To accomplish this, we provide a
strategy where a MTL SuperNet is trained only once but allows crafting SubNets
that can be sampled based on the user’s MTL constraints (compute cost and task
preference) at test-time. “High” task preference for task $i$ implies the
performance for task $i$ is more important than other tasks.

Real-world MTL systems are seeing growing applications ranging from autonomous
cars [3] to video cameras for traffic analysis [4], with respective task
performance preferences. For example, observe Fig. 1. A single MTL
architecture can allow two users to use the same model but with custom task
preferences based on the available compute cost. The user with higher compute
(_e.g_. self-driving cars) may expect higher performance on task 1, but the
user with lower compute (_e.g_. traffic cameras) would prefer higher
performance on task 2 given the budget. It will be extremely inefficient to
create and train MTL architectures for all such possible variations of user
requirements due to expensive design and deployment costs [5, 6, 7]. This
brings forth the need for flexible MTL architectures that allow test-time
trade-offs based on relative task importance and resource allocation. Some
prior methods have introduced dynamic MTL networks [8, 9, 10, 11] in an effort
to incorporate changing user task preferences at test-time. However, such
methods do not account for changing the user’s computational budget as they
assume fixed computation cost resulting in limited applicability. Recently,
Controllable Dynamic Multi-task Architecture (CDMA) [7] introduced a multi-
stream (equal to number of tasks) architecture to handle both changing task
preferences and compute budgets. For controllability, it adjusts branching
locations in the encoder and generates encoder weights using external
hypernetworks [12] while fixing decoders. In this paper, we propose a multi-
task method called ‘Efficient Controllable Multi-Task architectures’ (ECMT)
that consists of a shared encoder and task-specific decoders where the channel
widths of both modules are slimmable [13]. Our key idea is to control the task
importance by varying the capacities of task-specific decoders while
controlling the compute budget by jointly adjusting the encoder capacity. This
is based on our observation that a larger backbone achieves overall higher
multi-task accuracy (even with task conflicts) compared to separately trained
multiple smaller backbones. Further, in contrast to adjusting the branching
points of multiple encoder streams [7], our approach can achieve overall
higher controllability by adopting one stronger backbone for a given compute
budget. Since decoder widths affect both accuracy and computational cost by a
considerable amount, especially for dense prediction tasks, adjustment of
decoder capacities is sufficient to control the task preferences. Constraining
to control the task preference only through the decoder capacities further
avoids adversarial effects when changing the shared encoder as it may cause
different effects to each task, which is hard to control. Finally, adjusting
both decoder and encoder largely increases the control over the computational
cost.

As the training is performed only once and the encoder is shared among tasks,
ECMT optimizes the sub-architectures by distilling [14] the encoder knowledge
of the parent architecture, that is capable of handling task conflicts given
its large capacity [15, 16, 17]. In particular, it uses a novel ‘Configuration
Invariant knowledge distillation’ (CI-KD) strategy to make the embeddings of
the shared encoder invariant to the varying sub-architecture configuration. At
test-time, ECMT uses the joint constraints and extracts a sub-architecture by
searching for the most suitable encoder and decoder width configuration using
the proposed evolution-based algorithm [18] designed for MTL models. The key
rule for the search algorithm is to provide a larger computational budget to
the higher preferred task decoder, while searching a shared encoder
configuration that enhances overall MTL performance.

Interestingly, without any need for external hypernetworks (to predict large
tensor weights of the parent architecture) and with a shared encoder (that
allows task scalability), ECMT demonstrates strong task preference \- task
accuracy \- efficiency trade-offs. Our extensive experiments on benchmark
datasets demonstrate strong MTL controllability across a wide range of joint
preferences (_e.g_., an increase in Hypervolume [19] of $\sim$34% is observed
when compared to state-of-the-art [7] during testing in the NYUD-v2 dataset
[20]). To summarize, our contributions in this paper are:

  1. 1.

We present a new method to sample high-performing efficient MTL sub-
architectures from a single MTL SuperNet that can satisfy both user
preferences of task performance and computational budget, dynamically without
retraining.

  2. 2.

Our method includes two key components:

    1. $\bullet$

A training strategy to enhance the MTL performance of sub-architectures in
order to have minimal performance drop even if user’s constraints become
restricted. In particular, it uses a CI-KD loss to transfer the encoder
knowledge of the parent model, which is capable of handling multi-task
conflicts, to the encoders of sub-models.

    2. $\bullet$

A subsequent search strategy that translates the task preferences to sample
the task decoders for better performance and searches for shared encoder width
configuration that supports the decoders for overall better MTL performance.

  3. 3.

We show superior controllability on sampling sub-models compared to prior
methods. For example, we show a higher controllability by $\sim$ 33.5% in the
NYU-v2 [20] (3 tasks) dataset and $\sim$ 55% in Pascal-Context [21] (5 tasks)
dataset over state-of-the-art method CDMA [7].

##  2 Related Works

#### Multi-task Learning (MTL).

Growing demands for MTL capable systems has led to a huge growth in methods
for designing effectual architectures that can leverage shared feature
representations [22, 1, 2] among tasks. Broadly, either these methods (a) [23,
24, 25, 26, 27, 28, 29] provide individual encoders (with respective decoders)
for each task and optimize to decrease the distance between the parameters
(soft sharing), or (b) optimize a single (shared) encoder for all tasks [30,
31, 32, 11, 33, 34, 35] followed by individual decoders (hard sharing). A
significant number of prior works mainly focus on building MTL strategies
under static (or fixed) task preference and compute budget. Hence, any change
in these constraints results in re-training the model from scratch. In order
to save on designing costs and stringently follow user requirements, some
prior works have presented strategies to obtain custom MTL architectures by
search mechanisms [36, 37, 38, 39, 40, 41, 42, 43] similar to traditional
neural architecture search (NAS). Such MTL NAS methods are designed for a
single model matching only one compute budget and are unsuitable for dynamic
changing requirements. Different from these, we aim to provide a novel
solution for MTL under dynamic (or changing) task preference and compute
budget without re-training.

#### Controllable MTL Neural Networks.

[7, 11, 32, 9, 44] have proposed controllable MTL architectures where a parent
network is trained to extract sub-architectures that follows user’s
constraints without re-training. For example, [9, 44] presented strategies to
train hypernetworks to predict weights of a MTL SuperNet in order to match
user’s changing task performance preference. A major drawback of these
approaches is that they assume a static compute budget, making them incapable
of handling dynamic compute resources. Some prior single task learning (STL)
methods such as Once-for-all networks [5] and BigNAS [6] provide train and
search strategies for dynamic compute resources. However, by design they do
not provide any recipe for incorporating user MTL task preferences. In short,
none of these aforementioned works provide all of dynamic and multi-task
aspect as ECMT. Different from [9, 44, 32], CDMA [7] presented a method to
handle multiple or joint MTL user constraints where both task preference and
compute budget constraints are dynamic. It uses two hypernetworks to predict
both network architecture and parameters to match joint constraints. Further,
its parent model follows the soft-parameter sharing MTL setup. As a result,
CDMA requires additional memory overhead due to two external hypernetworks,
faces scalability issues due to soft sharing of encoder, and doesn’t consider
the decoder in it’s search space. Better than CDMA, ECMT uses a novel training
paradigm for hard-parameter sharing MTL architecture and uses a simple
strategy to sample high performing sub-architectures. The search space is
defined by the layer width [45, 13] and encompasses both the shared encoder
and the task decoders.

Figure 2: Illustration of our pipeline. Our overall pipeline to obtain MTL
SubNets is presented. In (A), we present the SuperNet training strategy where
we train the MTL SuperNet collaboratively with the MTL SubNets. We propose a
knowledge distillation loss to transfer the knowledge of the largest capacity
encoder, which has less task conflicts, to smaller capacity encoders of the
SubNets. In (B), we demonstrate our novel strategy to search SubNets (both the
shared encoder and decoders) based on the user’s joint constraints (task
preference and available compute budget). In (C), the search algorithm can
provide SubNets as per multiple user preferences.

#### Slimmable Neural Networks.

Slimmable networks [13, 45, 46] proposed a method to train STL neural networks
to support operating using different filter levels controlled by width (or
number of filters) multipliers; e.g., a width multiplier 0.5 ‘slims’ down all
the parent model layers resulting in a sub-network that has 50% of filters.
These width multipliers are uniform across the architecture, and can be tuned
to match the user’s memory budget with minimal performance degradation. This
strategy has inspired solutions for various STL research areas such as
generative adversarial networks [47], semantic segmentation [48] and others
[49, 50]. Similar to [13], [5, 6] explored different freedom directions such
as depth and kernel sizes to achieve strong accuracy-efficiency trade-off in
STL setup. While we leverage the idea of slimmable models, ECMT is strikingly
different from the aforementioned works as they do not support the capability
of task performance preference trade-off. Further, [49, 50, 5, 6] have been
mostly explored only for classification tasks. ECMT is designed for MTL setup
that extends beyond classification tasks to dense prediction tasks.

##  3 Problem Statement

#### Notations.

We denote data distribution as composed of training set $\mathcal{D}_{tr}$,
validation set $\mathcal{D}_{val}$, and testing set $\mathcal{D}_{te}$ with
$N$ tasks. Each task shares the input image $\bm{x}$ with corresponding
outputs $\mathcal{Y}=$ {$\bm{y}_{1}$, $\bm{y}_{2}$, $\cdots$, $\bm{y}_{N}$}.
We create a MTL parent architecture or SuperNet $\mathcal{S}$ composed of a
single shared encoder among tasks and $N$ task decoders. $\mathcal{S}$ is end-
to-end non-uniformly slimmable: every layer can be tuned to have it’s own set
of filters $\mathcal{F}$ (also called width [13]) which is independently
controlled by a separate width ratio $\omega\in(0,1]$. Let
$\mbox{\Large$\bm{\omega}$}=[\omega_{\min},\cdots,\omega_{\max}]$ be the set
of possible values of width ratios with $\omega_{\max}$ ($\omega_{\min}$)
representing the maximum (minimum) possible values. A sub-network or SubNet
$\mathcal{S}^{(\zeta)}$ can be created from $\mathcal{S}$ by setting width
ratios for all $L$ layer denoted using a $L$-tuple
$\mathcal{S}^{(\zeta)}=\langle\omega^{(\zeta)}_{1},\omega^{(\zeta)}_{2},\cdots,\omega^{(\zeta)}_{L}\rangle\in\mbox{\Large$\bm{\omega}$}\times\mbox{\Large$\bm{\omega}$}\times\cdots\mbox{\Large$\bm{\omega}$}$.
Let the set of loss functions for the $N$ tasks be
$\\{\mathcal{L}_{1},\mathcal{L}_{2},\cdots,\mathcal{L}_{N}\\}$. Formally, task
preference indicates amount of available compute budget for the given task. We
denote the task preference list be
$\mbox{\Large$\bm{\tau}$}=[\tau_{1},\tau_{2},\cdots,\tau_{N}]$ with
$\tau_{i}\in[0.0,1.0]$, where higher value indicates higher preference.
Finally, we denote the weights of $\mathcal{S}$ as $\bm{\theta}$.

#### Problem Statement.

Our goal is to train the MTL SuperNet $\mathcal{S}$ that allows crafting
multiple MTL SubNets $\mathcal{S}^{(\zeta)}$ operable for a wide range of
joint MTL user budgets (compute budget $F_{user}$, and task preference
$\mbox{\Large$\bm{\tau}$}_{user}$) with minimal performance drop. The SuperNet
$\mathcal{S}$ (and the SubNets $\mathcal{S}^{(\zeta)}$) takes image $\bm{x}$
as input and predicts $N$ task outputs $\mathcal{Y}$. To train $\mathcal{S}$,
we define the following problem:

$\displaystyle\operatorname*{arg\,min}_{\bm{\theta}}~{}~{}\underset{\bm{x},\mathcal{Y}\sim\mathcal{D}_{tr}}{\mathbb{E}}\sum_{n=1}^{N}\rho_{n}\mathcal{L}_{n}\big{(}\bm{\theta}\big{)}$
(1)

Here, $\rho_{n}$ is the weight of $n^{th}$ task loss. Once $\mathcal{S}$ is
trained, the joint constrained search for obtaining $\mathcal{S}^{(\zeta)}$
can be expressed as the following problem:

$\displaystyle\min_{\mathcal{S}^{(\zeta)}}~{}~{}\underset{\bm{x},\mathcal{Y}\sim\mathcal{D}_{val}}{\mathbb{E}}\sum_{n=1}^{N}\rho_{n}\mathcal{L}_{n}\big{(}\mathcal{S}^{(\zeta)}\big{)}$
$\displaystyle\begin{aligned} \text{s.t.
}\text{compute}(\mathcal{S}^{(\zeta)})\leq F_{user},\\\ \text{task
preference}(\mathcal{S}^{(\zeta)})=\mbox{\Large$\bm{\tau}$}_{user}\end{aligned}$
(2)

##  4 Proposed Method

During training, we solve the problem in Eq. 1 by constructing a SuperNet
$\mathcal{S}$ parameterized by layer-wise width ratios in $\bm{\omega}$ (see
Sec. 4.1). During inference, we solve Eq. 2 by searching for the most suitable
encoder and decoder width configuration using an evolution-based search
algorithm based on the joint constraints (see Sec. 4.2). The training is
performed only once, whereas the search is performed for each deployment
scenario.

###  4.1 Training the MTL SuperNet

#### Overview.

Fig. 2-(A) provides an overview of the proposed training pipeline. At its
core, the training strategy aims to enhance the MTL performance of the SubNets
sampled from the SuperNet in order to have minimal performance drop even if
user’s constraints become restricted. To this end, we leverage the Sandwich
Rule (SR) training [45] and make necessary modifications for our MTL setup. In
particular, it involves a novel (width) configuration-invariant knowledge
distillation loss aimed at teaching the SubNet encoders from the SuperNet
encoder. We now discuss the pipeline in detail.

#### Training with the Sandwich Rule.

The SR training [45] for single-task learning (STL) requires that in each
training iteration, we update the SuperNet with the collectively accumulated
loss gradients of the model at $b$ widths. We follow [45] and choose $b=4$
which includes the model at largest width $\omega_{\max}$, smallest width
$\omega_{\min}$, and $b-2$ randomly chosen models at non-uniform widths.
Further, the STL SubNets in SR [45] are optimized only using the predictions
of the largest width model (_i.e_. SuperNet). We build upon this rule and
introduce the following changes.
In contrast to the aforementioned, we enforce each SubNet to learn the MTL
data distribution directly from the available ground-truth labels $\bm{y}$.
The training loss of collective learning (_i.e_. training each SubNet as the
SuperNet from ground-truth labels) is denoted as
$\mathcal{L}_{\mathchoice{\raisebox{0.0pt}{\leavevmode\resizebox{15.35486pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.35486pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.35492pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.35486pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\texttt{co}\mathstrut$}}}}}}$.
Training SubNets with ground-truth labels helps us avoid the following
pitfall: we do not need to train the MTL SubNets from the output predictions
of a weak parent MTL model (i.e. predictions in the initial iterations can be
weak as it is being trained from scratch). We could tackle this by training
the parent model standalone, but this is contrary to our goal of saving on
design costs of training once. Furthermore, we could also adopt knowledge
distillation strategies proposed in prior MTL works [51, 52]. However, doing
so would create additional training overhead for STL models for each task,
which is also not our end-goal. Hence, we present a new methodology of
distilling the knowledge of the parent model $\mathcal{S}$ to SubNets without
using output predictions, which brings us to our proposed encoder-based
knowledge distillation (KD) loss.

#### Configuration Invariant KD (CI-KD) Loss.

Our CI-KD loss is an in-place distillation loss
$\mathcal{L}_{\mathchoice{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92007pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\texttt{kd}\mathstrut$}}}}}}$,
which transfers the encoder knowledge of $\mathcal{S}$ to the encoders of sub-
networks $\mathcal{S}^{(\zeta)}$. The encoder of $\mathcal{S}$ is capable of
handling multi-task conflicts due to its high capacity [15, 16, 17] and we aim
to teach the encoders of the smaller models from its features. In particular,
we propose to minimize distance between the encoder features computed from
parent model $\mathcal{S}$ and all the $i$th child model involved in the
sandwich setup. Now, this loss cannot be directly estimated: the features of
$\mathcal{S}$’s encoder $\bm{z}$ and other child models $\bm{z}^{(i)}$ are of
different sizes due to the different configurations of the SubNet encoders. To
make the shared encoder feature size configuration invariant, we compute the
average features along the channel dimensions for all models in the Sandwich.
We then minimize the mean square error loss between these channel-averaged
features of the parent model and the $b-1$ child models as follows.

$\displaystyle\mathcal{L}_{\mathchoice{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92007pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\texttt{kd}\mathstrut$}}}}}}=\dfrac{1}{b-1}\sum_{i}^{b-1}\text{~{}MSE}(\widehat{\bm{z}},\widehat{\bm{z}}^{(i)})$
(3)

Here, $\widehat{\bm{z}}$ and $\widehat{\bm{z}}^{(i)}$ are the encoder features
of $\mathcal{S}$ and $i$th child model (in the Sandwich), averaged along the
channel dimension. Note that $\widehat{\bm{z}}$ is detached from the
computational graph as we do not intend to update the parent model with
$\mathcal{L}_{\mathchoice{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92007pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\texttt{kd}\mathstrut$}}}}}}$.
This distillation loss has been illustrated in Fig. 3. To summarize, the
SuperNet learning loss only includes Eq. 1, whereas the $i^{th}$ SubNet
learning loss includes both with Eq. 1 and
$\lambda\mathcal{L}_{\mathchoice{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92007pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\texttt{kd}\mathstrut$}}}}}}$
($\lambda$ is the weight of the CI-KD loss). The training algorithm is given
in Algo. 1.

Algorithm 1 ECMT training for SuperNet $\mathcal{S}$.

1:Width list $\bm{\omega}$,  _e.g_. $[0.3,0.4,\cdots 1.0]$.

2:Number of models $b$ in Sandwich Rule,  _e.g_., $b=4$.

3:for $t=1,\cdots,T_{epoch}$ do

4: Get input image $\bm{x}$ and task labels $\mathcal{Y}$.

5: Clear gradients, optimizer.zero_grad().

6: Get task outputs & enc. feature $\bm{z}$ from $\mathcal{S}$;
$\widehat{\mathcal{Y}},\bm{z}=\mathcal{S}(\bm{x})$.

7: Get total loss
$\mathcal{L}_{\mathchoice{\raisebox{0.0pt}{\leavevmode\resizebox{15.3549pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.3549pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.35487pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.35487pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\texttt{co}\mathstrut$}}}}}}$
using {$\widehat{\mathcal{Y}},\mathcal{Y}$} in Eq. 1.

8: Accumulate gradients,
$\mathcal{L}_{\mathchoice{\raisebox{0.0pt}{\leavevmode\resizebox{15.3549pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.3549pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.35487pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.35487pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\texttt{co}\mathstrut$}}}}}}$.backward().

9: Stop gradients of $\bm{z}$, $\bm{z}=\bm{z}.\texttt{detach()}$.

10: Randomly sample ($b-1$) models
{$S_{b}=\mathcal{S}^{(1)},\cdots,\mathcal{S}^{(b-1)}$}.

11: Add smallest width model to $S_{b}$.

12: for $\mathcal{S}^{(i)}$ in $S_{b}$ do

13: Get task outputs & enc. feature $\bm{z}$ from $\mathcal{S}^{(i)}$

14: Compute loss
$\mathcal{L}^{(i)}=\mathcal{L}_{\mathchoice{\raisebox{0.0pt}{\leavevmode\resizebox{15.3549pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.3549pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.35487pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.35487pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\texttt{co}\mathstrut$}}}}}}+\lambda\mathcal{L}_{\mathchoice{\raisebox{0.0pt}{\leavevmode\resizebox{10.92003pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92003pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92003pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\texttt{kd}\mathstrut$}}}}}}$.

15: Accumulate gradients, $\mathcal{L}^{(i)}.\texttt{backward()}$.

16: end for

17: Update SuperNet weights, optimizer.step().

18:end for

###  4.2 Searching based on Joint User Preferences

#### Overview.

Fig. 2-(B) provides a simple method to sample sub-networks that follow the
user’s joint constraints of task preference $\mbox{\Large$\bm{\tau}$}_{user}$
and compute budget $F_{user}$. We divide the search into two parts. In Step 1,
we sample the width ratios of the task decoders based on the user’s task
preference using a simple rule proposed in Eq. 4. With the decoder
configuration fixed, we search for an optimal shared encoder configuration in
Step 2. The goal of the search is to support the sampled task decoders for
better performance than randomly choosing the configuration while satisfying
the overall compute budget. Step 2 particularly involves a MTL accuracy
predictor that provides quick feedback on the overall model configuration
during the search cycle and saves repeated evaluation related computations. We
now expand on each step in detail.

####  Step 1: Setting the task decoders.

We propose to set the width ratios of the task decoders based on the task
preference $\mbox{\Large$\bm{\tau}$}_{user}=\\{\tau_{i}\\}_{i}^{N}$ as they
are independent for each task. In particular, we map each $\tau_{i}$ to the
discrete uniform range of
$\mbox{\Large$\bm{\omega}$}\sim\mathcal{U}(\omega_{\min},\omega_{\max})$.
Assuming $\mbox{\Large$\bm{\tau}$}\sim\mathcal{U}(0,1)$ as a uniform
distribution with unit density when $0\leq\tau\leq 1$ (0 otherwise),
$\tau_{i}$ is mapped to a decoder width ratio $\omega_{i}$ as:

$\displaystyle\omega_{i}=\omega_{\min}+(\omega_{\max}-\omega_{\min})\tau_{i}$
(4)

Clearly, $\omega_{i}\propto\tau_{i}$ _i.e_. the decoder of the task with
higher preference will be assigned a higher width ratio. This design choice is
motivated by the reason to allow a larger computational budget in the
available user’s budget to the higher preferred task decoder. Once all the
decoders are fixed using Eq. 4, we search for a shared encoder width
configuration to support the aforementioned width decoder configuration.

Figure 3: Illustration of our Configuration Invariant Knowledge Distillation
(CI-KD) Loss. This loss encourages the shared encoder features to be invariant
of the $i^{th}$ SubNet capacity, by enforcing them to be close to the
SuperNet’s shared encoder features.

####  Step 2: Searching for the shared encoder.

The aim is to sample a width ratio configuration for the shared encoder, that
supports the best performance out of the sampled decoders. Randomly choosing
the encoder configuration is one possible option, but it doesn’t necessarily
result in the best architecture due to our large search space. In order to
leverage the large search space designed by our non-uniform layer setup and
find a better performing model, we use an evolution-based search algorithm
[18]. The search algorithm consists of three key components. First, we
initialize a pool $\mathcal{P}$ of $P$ models
($\mathcal{P}=\\{\mathcal{S}^{(1)},\mathcal{S}^{(2)},\cdots,\mathcal{S}^{(P)}\\}$),
all with the fixed decoder configuration obtained from Step 1. Each of these
models are characterized by the same width ratio across all encoder layers.
Next, we evolve $\mathcal{P}$ in order to find a better performing model than
the initialized ones by leveraging the flexibility of choosing width ratios
for each layer mutually exclusively in $\mathcal{S}^{(\zeta)}$. We randomly
choose $K<L$ encoder layers and change the width ratio $\omega_{k}$ by the
rule:

$\displaystyle\widehat{\omega}_{k}=\omega_{k}+\eta\text{
sign}(F_{user}-F^{(\zeta)})$ (5)

Here, $F^{(\zeta)}$ is the computational cost of $\mathcal{S}^{(\zeta)}$
(_e.g_. GMACs), $F_{user}$ is the computational budget set by the user, and
sign($\cdot$) extracts the sign of the input variable.We set $\eta=0.1$ as we
use the design specification $\omega_{i}-\omega_{j}=0.1$. The motivation of
this design choice is to push the shared encoder configuration towards larger
capacity, which are known to handle task conflicts better [15, 16, 17]. This
evolution step creates a new model $\widehat{\mathcal{S}^{(\zeta)}}$ which is
added back to $\mathcal{P}$. In the end, the best performing model from the
search is provided for deployment. At all steps, we ensure that each model
$\mathcal{P}$ satisfies the user’s compute budget constraint. In order to
quickly evaluate the quality of models in $\mathcal{P}$, we build a subsidiary
neural network $\mathcal{R}$ that provides a feedback on
$\widehat{\mathcal{S}^{(\zeta)}}$’s approximate MTL performance. This MTL
accuracy predictor $\mathcal{R}$ eliminates the need for repeated cost of
getting the measured accuracy by providing a predicted accuracy. Specifically,
$\mathcal{R}$ is optimized to take $\mathcal{S}^{(\zeta)}$’s width
configuration as input and predict the approximate performance of this
configuration [5]. To train $\mathcal{R}$, we first create $K$ examples of
[$\mathcal{A}^{(\zeta)}$, ($\mathcal{L}_{1},\cdots,\mathcal{L}_{N}$)] pairs by
randomly sampling $M$ SubNets with different configurations
$\mathcal{A}^{(\zeta)}$, and computing their task losses on
$\mathcal{D}_{val}$. $\mathcal{A}^{(\zeta)}$ contains the list of width ratios
computed for the shared encoder and the task decoders. In our experiments, we
choose $M=2000$. The architecture of $\mathcal{R}$ has been provided in Algo.
3 and training procedure is provided in Sec. 5. Note that, we only need to
collect the data pairs and train $\mathcal{R}$ once, making this overhead
negligible in comparison to training $\mathcal{S}$. Further, this cost remains
constant regardless of changing user requirements. Fig. 2-(C) provides some
examples of the resultant MTL architectures.

Algorithm 2 ECMT SubNet search.

1:MTL Accuracy Predictor $\mathcal{R}$, Number of search cycles $T_{cycle}$

2:Model pool size $P$

3:User MTL constraints ($F_{user},\mbox{\Large$\bm{\tau}$}_{user}$)

4:Compute and fix decoder widths using $\mbox{\Large$\bm{\tau}$}_{user}$ using
Eq. 4.

5:Initialize the model pool $\mathcal{P}$ with $P$ random encoder widths,
including uniform encoder widths, that satisfy memory constraint $F_{user}$

6:Get the most preferred task $\mathcal{T}$ =
$\max(\mbox{\Large$\bm{\tau}$}_{user})$

7:for $t=1,\cdots,T_{cycle}$ do

8: Randomly choose a model $\mathcal{S}^{(i)}$ from $\mathcal{P}$

9: Change the width of a randomly chosen encoder layer with Eq. 5 in
$\mathcal{S}^{(i)}$ and create $\widehat{\mathcal{S}^{(\zeta)}}$

10: Add the mutated model $\widehat{\mathcal{S}^{(\zeta)}}$ to $\mathcal{P}$

11: Delete the worst model (which results in highest loss in the preferred
task $\mathcal{T}$) computed using $\mathcal{R}$.

12:end for

13:Return the width configuration of the best performing model in
$\mathcal{P}$ predicted using $\mathcal{R}$.

We summarize our proposed MTL search algorithm in Algo. 2. In Algo. 2, we call
a candidate model “mutated” (in Line 7) when we change a random encoder layer
(in Line 6).

##  5 Experiments

In this section, we demonstrate the ability of ECMT to extract efficient
architectures based on a user’s joint multi-task learning preferences. We show
that our proposed framework can scale to a large number of tasks while
allowing proficient task preference \- task accuracy \- efficiency trade-off
with a single MTL model. Through extensive experiments on three datasets with
various architectures, we provide new insights to the community regarding
controllable MTL architectures which can be re-used for diverse deployment
scenarios without re-training.

#### Training implementation details.

We use PyTorch [53] for our implementation.

  1. $\bullet$

NYUD-v2 and Pascal-Context. We follow [2] to set the following
hyperparameters. The SuperNet is trained with Adam Optimizer [54] with
learning rate $0.0001$, and weight decay $0.0001$. We use a poly learning rate
scheduler. We set the total epochs $T_{epochs}$ as 100 for PASCAL-
Context/NYUD-v2. The training batch size is set to 8. The task loss weights
$\rho_{n}$ are set as follows- NYU-v2 $\rightarrow$ Semantic segmentation: 1,
Depth: 1, and Surface normals: 10; PASCAL-Context $\rightarrow$ Semantic
segmentation: 1, Human parts segmentation: 2, Saliency: 5, Edge: 50, Surface
normals: 10. The training data augmentations are set from [41]. We further add
Random Erasing [55] with probability 0.5 to the aforementioned. The shared
encoder is initialized with ImageNet [56] pre-trained weights, whereas the
decoders are trained from scratch. The CI-KD loss weight $\lambda$ is set to 1
and 0.001 for NYUD-v2 and Pascal-Context, respectively. $\bm{\omega}$ is set
as $[0.6,0.7,\cdots,1.0]$ for NYUD-v2, and $[0.5,0.6,\cdots,1.0]$ for Pascal-
Context. The input channels to the DeepLabv3 decoder for NYUD-v2 and Pascal-
Context are set to 256 and 128, respectively.

  2. $\bullet$

CIFAR100. All the task loss weights are set to 1. The batch size is set to
256. We set the total epochs $T_{epochs}$ is set as 75. The SuperNet is
trained with Adam Optimizer [54] with learning rate $0.001$, and weight decay
$0.0001$. The whole SuperNet is trained from scratch. The CI-KD loss weight
$\lambda$ is set to 0.01. $\bm{\omega}$ is set as $[0.2,0.3,\cdots,1.0]$.

All experiments use 90% of training set for all datasets. All other
hyperparameters are set as per default PyTorch settings.

#### Evaluation criteria.

Following [7], we use hypervolume (HV) [19] to measure controllability with
respect to task preferences. HV helps to evaluate the preference-loss trade-
off curve (or Pareto-front [11]) among the different tasks in the loss space
[57]. Basically, HV accounts for both the quality of the models (volume they
dominate), and also the diversity, measured in the overlap between dominated
regions. Higher value indicates better controllability assuming same memory
budget. Bold values indicate best results.

#### Inference implementation details.

For comparisons with CDMA and PHN for controllability, we follow CDMA’s method
of task preference sampling. In particular, we sample task preferences
$\tau\sim P_{\tau}$, where $P_{\tau}$ is a Dirichlet distribution of order $N$
with parameters $[\alpha_{1},\alpha_{2},\cdots,\alpha_{N}]$ ($\alpha_{i}>$ 0).
Following [7], we set $\alpha_{i}=0.2~{}\forall~{}i$ for PASCAL-
Context/NYUD-v2, and $\alpha_{i}=1.0~{}\forall~{}i$ for CIFAR100. HV is
computed across 20 task preferences following [7]. DeepSpeed [58] is used to
compute the architecture GMACs. For any $\mbox{\Large$\bm{\tau}$}_{user}$, we
always aim to set the highest width for most preferred task for best results.
Hence, we min-max norm $\mbox{\Large$\bm{\tau}$}_{user}$ before using Eq. 4.
Any value $\in[0,1]$ can be used for each task preference (sum need not be 1).
We set the number of search cycles $T_{cycle}$ as 150 for CIFAR100 and 10 for
NYUD-v2/Pascal-Context. We set the model population size to 50. The search
runtime is proportional to $T_{cycle}$.

#### Datasets.

We conduct our experiments using three multi-task datasets, namely PASCAL-
Context [21] (5 tasks) and NYU-v2 [20] (3 tasks), and CIFAR-100 [59, 60] (20
tasks). The PASCAL-Context dataset provides joint semantic segmentation, human
parts segmentation, saliency estimation, surface normal estimation, and edge
detection. The NYU-v2 dataset provides joint semantic segmentation, depth
estimation and surface normal estimation. The CIFAR-100 (MTL) dataset provides
a split of 20 five-way classification tasks extracted from the original
dataset. Semantic segmentation, saliency estimation and human parts
segmentation are evaluated using mean intersection over union (mIoU). Depth
estimation and surface normals are evaluated using the root mean square error
(rmse).

Algorithm 3 Pseudocode of our MTL Accuracy Predictor $\mathcal{R}$.

    import torch.nn as nn

    # ----- multi-task performance predictor
    class AccuracyPredictor(nn.Module):
        def __init__(self, input_channels: int,
                           task_names: list):
            super().__init__()
            self.model = nn.Sequential(
                nn.Linear(input_channels, 100),
                nn.ReLU(),
                nn.Linear(100, 100),
                nn.ReLU(),
                nn.Linear(100, 50),
                nn.ReLU()
            )

            self.task_names = task_names

            self.heads = nn.ModuleDict({task:
                      nn.Linear(50, 1) for task in
                      self.task_names})

        def forward(self, widths: torch.Tensor):
            feats = self.model(widths)
            preds = {t_id: self.heads[t_id](feats)
                  for t_id in self.task_names}

            return preds

#### Baselines.

As reported in Sec. 2, CDMA [7] is our main baseline which designs MTL
architectures, jointly controllable with task preference and memory
constraint. Further, we compare with PHN [44] (and its variation PHN-BN [7,
44]), which only allow task controllability. PHN uses a hypernetwork to
predict the weights of a shared backbone based SuperNet conditioned on a task
preference. Further, we also compare with MTL-Static models trained for
highest user constraints. It provides the upper bound of the HV ECMT can
achieve. The MTL-Static models and ECMT are trained with 90% samples of the
original training split. The other 10% split is used to train the MTL accuracy
predictor.

#### Architectures.

Our SuperNet $\mathcal{S}$ consists of a shared encoder (backbone) with $N$
task decoders. For dense prediction tasks (PascalContext, NYUD-v2), we use the
DeepLabv3 architecture [61] for each task, whereas we use linear layers for
classification tasks (CIFAR100-MTL). We follow CDMA and choose the backbone
architectures as MobileNetV2 [62] for PASCAL-Context, ResNet34 [63] for
NYUD-v2, and ResNet9 [64] for CIFAR100-MTL. MobileNetV2 and ResNet34 are pre-
trained on ImageNet [56]. Note that, in all cases, both the encoder and the
task decoders are non-uniformly slimmable. Following [45, 6], we do not
accumulate batch norm statistics while training the SuperNet as these are ill-
defined due to varying SubNet configurations. During testing, we re-calibrate
the batch norm statistics for each SubNet without any fine-tuning of its
parameters.

#### MTL accuracy predictor details.

The MTL accuracy predictor $\mathcal{R}$ is a three layer feed-forward neural
network summarized in Algo. 3. Given a SubNet model $\mathcal{S}^{(\zeta)}$,
we create a list $\mathcal{A}^{(\zeta)}$ consisting of width ratios starting
with the shared encoder, followed by the decoder’s width ratios.
$\mathcal{A}^{(\zeta)}$ is then fed to the $\mathcal{R}$ to get the predicted
MTL accuracy for all $N$ tasks. To train $\mathcal{R}$, we first create
$M=2000$ examples of [$\mathcal{A}^{(\zeta)}$,
($\mathcal{L}_{1},\cdots,\mathcal{L}_{N}$)] pairs by randomly sampling $M$
SubNets with different configurations $\mathcal{A}^{(\zeta)}$, and computing
their task losses on $\mathcal{D}_{val}$. We train this predictor for 150
epochs using L1-loss using the Adam optimizer with a learning rate of $0.001$.
The batch size is set to 16.

Table 1: Evaluation on NYUD-v2. Reference point for HV: $[4,4,4]$. $\dagger$
indicates smaller compute cost (GMACs).

Method |  |  | GMACs
---
$(\downarrow)$
| Control
---
Params.$(\downarrow)$
|  | HV
---
$(\uparrow)$
PHN |  | 21.02 | 21.04M |  | 02.36
PHN-BN |  | 21.02 | 02.23M |  | 11.72
CDMA† |  | 25.98 | 00.03M |  | 09.53
CDMA |  | 29.04 | 00.03M |  | 12.42
MTL-Static |  | 22.66 | - |  | 35.64
ECMT † |  | 10.00 | 00.20M |  | 34.91
ECMT |  | 20.00 | 00.20M |  | 34.89

Table 2: Evaluation on PascalContext. Reference point for HV: $[3,3,3,3,3]$.
$\dagger$ indicates smaller compute cost (GMACs).

Method |  |  | GMACs
---
$(\downarrow)$
| Control
---
Params.$(\downarrow)$
|  | HV
---
$(\uparrow)$
PHN |  | 06.28 | 21.50M |  | 42.61
PHN-BN |  | 06.28 | 03.63M |  | 72.27
CDMA† |  | 06.81 | 15.32M |  | 73.20
CDMA |  | 07.21 | 15.32M |  | 75.52
MTL-Static |  | 09.43 | - |  | 242.79
ECMT † |  | 04.00 | 0.021M |  | 166.75
ECMT |  | 09.00 | 0.021M |  | 166.97

###  5.1 Comparison with Baselines

We present the overall multi-task performance of sampling sub-architectures
with three different distributions NYUD-v2 (3 tasks), Pascal-Context (5 tasks)
and CIFAR-100 (20 tasks) in Tab. 1-3. Here we compare with state-of-the-art
methods CDMA (allows compute budget controllability along with task
controllability), PHN and PHN-BN (allows only task controllability). Following
CDMA [7], we report HV (reference point set according to CDMA) across 20 task
preferences. Similar to CDMA, we analyze ECMT under both small and large
extremes of compute budgets (indicated using GMACs). We also account for the
external networks used to sample sub-architectures under ‘Control Parameters’.
For PHN and CDMA, this is the cost of the hypernetworks, while for ECMT, the
cost pertains to the MTL accuracy predictor $\mathcal{R}$. Note that results
for both CDMA and ECMT are computed from one model while varying compute and
task preference constraints.

Table 3: Evaluation on CIFAR100-MTL. Reference point for HV: $[1,1,\cdots,1]$.
$\dagger$ indicates smaller compute cost (GMACs)

Method |  |  | GMACs
---
$(\downarrow)$
| Control
---
Params.$(\downarrow)$
|  | HV
---
$(\uparrow)$
PHN |  | 073.13 | 11.03M |  | 0.002
PHN-BN |  | 073.13 | 00.31M |  | 0.007
CDMA† |  | 129.23 | 03.10M |  | 0.009
CDMA |  | 174.36 | 03.10M |  | 0.010
MTL-Static |  | 072.92 | - |  | 0.0089
ECMT † |  | 038.40 | 00.02M |  | 0.0026
ECMT |  | 072.92 | 00.02M |  | 0.0082

Figure 4: Loss curves comparison on NYUD-v2 (3 tasks). Due to strategy to
translate task preferences to task decoders, task losses remain low even if
the preference decreases. This supports our training paradigm to improve the
performance of the smaller architectures, not done in CDMA and PHN.

ECMT demonstrates high HV values compared to the existing methods, especially
in NYUD-v2 and Pascal-Context. The high HV along with lower GMACs supports our
claim that the proposed shared encoder and individual decoders are capable of
solving multi-task problems while handling task trade-offs. For example, ECMT
shows a higher HV by $\sim$ 33.5% in the NYUD-v2 dataset and $\sim$ 55% in
Pascal-Context dataset, while using comparatively much less compute in both
the cases. We believe this strong performance is due to our strategy to
incorporate task decoders in the search space which is ignored by CDMA. For
the classification task of CIFAR-100, ECMT achieves similar HV with lesser
compute cost. We believe that the impact of our task preference translation as
per Eq. 4 is smaller for CIFAR-100 given that the decoder of the classifier
(fully connected layers) is computationally lighter than dense prediction
decoders. Finally, our strategy to translate the task preferences to the
decoders allows us to maintain the HV even with highly restricted compute
cost. This is highly advantageous compared to PHN and CDMA, where the change
in control parameters or the compute cost deteriorates the HV.

Table 4: Ablation Study on NYUD-v2. $\mathcal{T}_{1}$: Semantic Seg.,
$\mathcal{T}_{2}$: Human-Parts Seg., $\mathcal{T}_{3}$: Depth Est., Here, the
colored row indicates performance of largest model for reference. Bottom two
rows indicate the impact of loss
$\mathcal{L}_{\mathchoice{\raisebox{0.0pt}{\leavevmode\resizebox{10.92001pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92001pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92001pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\texttt{kd}\mathstrut$}}}}}}$
on the performance of smallest possible models for our method. HV is computed
by keeping the budget indicated under GMACs for all the cases.

Learning Loss |  | GMACs |  | Task Performance |  | Control
---|---|---|---|---|---|---
$\mathcal{L}_{\mathchoice{\raisebox{0.0pt}{\leavevmode\resizebox{15.35486pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.35486pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.35492pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\texttt{co}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{15.35486pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\texttt{co}\mathstrut$}}}}}}$ | $\mathcal{L}_{\mathchoice{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92007pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\texttt{kd}\mathstrut$}}}}}}$ |  |  |  $\mathcal{T}_{1}$ ($\uparrow$) |  $\mathcal{T}_{2}$ ($\downarrow$) |  $\mathcal{T}_{3}$ ($\downarrow$) |  |  HV ($\uparrow$)
– | – |  | 22.66 |  | 36.03 | 26.82 | 0.63 |  | 34.86
✓ | ✗ |  |  |  | 30.35 | 28.86 | 0.70 |  | 32.87
✓ | ✓ |  | 08.39 |  | 32.38 | 28.52 | 0.67 |  | 33.81

Figure 5: Search algorithm comparison on NYUD-v2. Sematic seg.: higher and
Depth est.: lower is better. Our proposed search algorithm provides better
architectures with negligible search cost.

As the HV is a function of the loss values computed over changing task
preferences, we visualize the task preference - task loss trade-off curves in
Fig. 4. Due to our strategy to translate task preferences to task decoders,
the task losses remain low even if the task preference decreases. This is
because lower width SubNets (created due to lower task preferences) are
enhanced to perform closely to the SuperNet. This further attests to our
training paradigm to improve the performance of the smaller MTL architectures,
a feature absent in CDMA and PHN.

Figure 6: Saving design costs. NYUD-v2 (3 tasks) with ResNet34 backbone. Our
training method allows to sample multiple high performing MTL architectures
based on the user compute cost after training only once, in contrast to static
MTL/STL architectures where the training has to be repeated for changing
constraints.

###  5.2 Ablation Study

#### Effectiveness of CI-KD loss and shared encoder size.

In Tab. 4, we analyze the importance of proposed loss functions in our
SuperNet training using two different backbones. It can be observed that the
CI-KD loss
$\mathcal{L}_{\mathchoice{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92006pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\texttt{kd}\mathstrut$}}}}}{\raisebox{0.0pt}{\leavevmode\resizebox{10.92007pt}{7.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\texttt{kd}\mathstrut$}}}}}}$
pushes the performance of the smallest network towards the parent network for
both the cases. For example, for the ResNet34 backbone SuperNet, CI-KD loss
increases the semantic segmentation by almost 2 points whereas the HV
increases by 1 point for the smallest architecture with 37% less compute cost.

#### Effectiveness of our search strategy.

Our search algorithm is aimed to find the best shared encoder configuration
that supports the sampled task decoders based on Eq. 4. To show its efficacy,
we compare it with the strategy of choosing the width ratios of the encoder
randomly in Fig. 5 for the NYUD-v2 dataset. We train a MTL SuperNet with the
training set $\mathcal{D}_{tr}$. The ‘random’ search algorithm then samples
width ratios from the available width list $\bm{\omega}$ and chooses the
encoder configuration satisfying the user’s compute budget. Our proposed
search, on the other hand, uses the accuracy predictor $\mathcal{R}$ created
with the validation set $\mathcal{D}_{val}$ and chooses an optimal encoder
configuration that supports the decoder for best task performance. Note that
the time for our search strategy is negligible compared to training a sub-
architecture from scratch. Further, computation overhead due to our search
algorithm is only needed when the user preferences change and does not
influence the final inference time.

Figure 7: Marginal evaluation on NYU-v2. Our proposed method to translate task
preference to task decoders is effective in two encoder configurations
(largest, smallest). Different tasks have different response to encoder
configuration which shows the necessity of our search algorithm to find an
optimal encoder configuration.

#### Marginal task evaluation.

In Fig. 7, we visualize the task performance for ECMT when the task preference
changes, by marginalizing over preference values of the other tasks. This is
done for two extreme cases of the encoder configuration: by setting the
encoder widths to the largest and smallest size, respectively. Clearly, an
increase in task preference leads to an increase in the task performance. This
is a direct result of our proposed method to set the decoder width ratios
according to Eq. 4. Further, it also shows that different tasks respond
differently to the encoder configurations. For example, the task of semantic
segmentation performs almost similarly for the task preference range [0.2,
0.8] for the both configurations, whereas the other tasks clearly present a
bigger difference. This shows the necessity of our search algorithm to find a
better encoder configuration. Fig. 7 also shows the accuracy-compute trade-off
available per task.

#### Savings on design costs.

Along with the aforementioned advantages of task performance tradeoff, our
training method in Sec. 4 allows to sample multiple high performing MTL
architectures while training only once. This saves expensive training costs
and allows multiple deployments from one model. We demonstrate this feature of
ECMT in Fig. 6 for NYUD-v2 (3 task) dataset for ResNet34 backbone. Here, the
static MTL and STL architectures can only be used for a fixed compute budget.
In contrast, ECMT can operate with variable compute costs and gracefully
degrade in performance with decreasing budget. Note that one can further
enhance the MTL performance of our parent architecture using state-of-the-art
methods summarized in [2, 1].

#### Qualitative examples.

We visualize some examples of the task decoder widths computed using the task
preferences from Eq.(4) in Fig. 8. Each block represents the task decoder with
its selected width ratio for the given $\mbox{\Large$\bm{\tau}$}_{user}$. The
design choice of $\bm{\omega}$ for NYUD-v2 is $[0.6,0.7,\cdots,1.0]$.

Figure 8: Illustration of our task preference translation. We visualize the
width ratios computed for the task decoders for NYUD-v2 (3 tasks). Note that
we normalize the task preference using max-min normalization before computing
the decoder widths.

##  6 Conclusions

We tackle the problem of multi-task architecture deployment based on user
joint preferences (task performance and available compute). The core challenge
is to train the multi-task architecture once but permit instant customization
of the network for diverse preferences. We propose to train non-uniformly
slimmable MTL architectures parameterized by layer wise width configurations,
resulting in a large space of MTL architectures. At inference, we use an
evolution-based search algorithm to sample precise MTL sub-architectures based
on the joint preferences. In contrast to prior controllable MTL methods solely
focused on encoders and providing poor task scalability, our method uses a
shared encoder and the task decoders as part of search space. We show the
effectiveness of our method on various multi-task settings, providing large
search space for sampling efficient MTL models covering a wide range of MTL
preferences.

#### Limitations and Future Works.

Our work has the following limitations that presents new opportunities for
interesting future works. ECMT has only been explored for CNN based
architectures and should be investigated for transformer based models.
Further, the task relativity should be considered when extracting a sub-
network as it is considered an important factor in MTL.

#### Acknowledgements.

This work was a part of Abhishek Aich’s internship at NEC Labs America. This
work was also partially supported by NSF grant 1724341. We would like to thank
the authors of [5] for providing the implementations related to accuracy
predictor used in their paper.

## References

  * Zhang and Yang [2021] Yu Zhang and Qiang Yang.  A survey on multi-task learning.  _IEEE Transactions on Knowledge and Data Engineering_ , 34(12):5586–5609, 2021.
  * Vandenhende et al. [2021] Simon Vandenhende, Stamatios Georgoulis, Wouter Van Gansbeke, Marc Proesmans, Dengxin Dai, and Luc Van Gool.  Multi-task learning for dense prediction tasks: A survey.  _IEEE transactions on pattern analysis and machine intelligence_ , 44(7):3614–3633, 2021.
  * Karpathy [2019] Andrej Karpathy.  Multi-task learning in the wilderness.  _ICML. url: https://slideslive. com/38917690/multitask-learning-in-the-wilderness_ , 2019.
  * Chen et al. [2019] Qiong Chen, Zimu Zheng, Chuang Hu, Dan Wang, and Fangming Liu.  On-edge multi-task transfer learning: Model and practice with data-driven task allocation.  _IEEE Transactions on Parallel and Distributed Systems_ , 31(6):1357–1371, 2019.
  * Cai et al. [2020] Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han.  Once for all: Train one network and specialize it for efficient deployment.  In _International Conference on Learning Representations_ , 2020.
  * Yu et al. [2020] Jiahui Yu, Pengchong Jin, Hanxiao Liu, Gabriel Bender, Pieter-Jan Kindermans, Mingxing Tan, Thomas Huang, Xiaodan Song, Ruoming Pang, and Quoc Le.  Bignas: Scaling up neural architecture search with big single-stage models.  In _ECCV_ , pages 702–717. Springer, 2020.
  * Raychaudhuri et al. [2022] Dripta S Raychaudhuri, Yumin Suh, Samuel Schulter, Xiang Yu, Masoud Faraki, Amit K Roy-Chowdhury, and Manmohan Chandraker.  Controllable dynamic multi-task architectures.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10955–10964, 2022.
  * Momma et al. [2022] Michinari Momma, Chaosheng Dong, and Jia Liu.  A multi-objective/multi-task learning framework induced by pareto stationarity.  In _International Conference on Machine Learning_ , pages 15895–15907. PMLR, 2022.
  * Lin et al. [2020] Xi Lin, Zhiyuan Yang, Qingfu Zhang, and Sam Kwong.  Controllable pareto multi-task learning.  _arXiv preprint arXiv:2010.06313_ , 2020.
  * Navon et al. [2020] Aviv Navon, Aviv Shamsian, Gal Chechik, and Ethan Fetaya.  Learning the pareto front with hypernetworks.  _arXiv preprint arXiv:2010.04104_ , 2020.
  * Mahapatra and Rajan [2020] Debabrata Mahapatra and Vaibhav Rajan.  Multi-task learning with user preferences: Gradient descent with controlled ascent in pareto optimization.  In _International Conference on Machine Learning_ , pages 6597–6607. PMLR, 2020.
  * Ha et al. [2016] David Ha, Andrew Dai, and Quoc V Le.  Hypernetworks.  _arXiv preprint arXiv:1609.09106_ , 2016.
  * Yu et al. [2018] Jiahui Yu, Linjie Yang, Ning Xu, Jianchao Yang, and Thomas Huang.  Slimmable neural networks.  _arXiv preprint arXiv:1812.08928_ , 2018.
  * Hinton et al. [2015] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_ , 2015.
  * Tang et al. [2022] Shengkun Tang, Yaqing Wang, Zhenglun Kong, Tianchi Zhang, Yao Li, Caiwen Ding, Yanzhi Wang, Yi Liang, and Dongkuan Xu.  You need multiple exiting: Dynamic early exiting for accelerating unified vision language model.  _arXiv preprint arXiv:2211.11152_ , 2022.
  * Xin et al. [2022] Derrick Xin, Behrooz Ghorbani, Ankush Garg, Orhan Firat, and Justin Gilmer.  Do current multi-task optimization methods in deep learning even help?  _arXiv preprint arXiv:2209.11379_ , 2022.
  * Kurin et al. [2022] Vitaly Kurin, Alessandro De Palma, Ilya Kostrikov, Shimon Whiteson, and M Pawan Kumar.  In defense of the unitary scalarization for deep multi-task learning.  _arXiv preprint arXiv:2201.04122_ , 2022.
  * Real et al. [2019] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le.  Regularized evolution for image classifier architecture search.  In _Proceedings of the aaai conference on artificial intelligence_ , volume 33, pages 4780–4789, 2019.
  * Zitzler and Thiele [1999] Eckart Zitzler and Lothar Thiele.  Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach.  _IEEE transactions on Evolutionary Computation_ , 3(4):257–271, 1999.
  * Silberman et al. [2012] Nathan Silberman, Derek Hoiem, Pushmeet Kohli, and Rob Fergus.  Indoor segmentation and support inference from rgbd images.  In _Proceedings of the European Conference on Computer Vision_ , 2012\.
  * Mottaghi et al. [2014] Roozbeh Mottaghi, Xianjie Chen, Xiaobai Liu, Nam-Gyu Cho, Seong-Whan Lee, Sanja Fidler, Raquel Urtasun, and Alan Yuille.  The role of context for object detection and semantic segmentation in the wild.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 891–898, 2014.
  * Ruder [2017] Sebastian Ruder.  An overview of multi-task learning in deep neural networks.  _arXiv preprint arXiv:1706.05098_ , 2017.
  * Misra et al. [2016] Ishan Misra, Abhinav Shrivastava, Abhinav Gupta, and Martial Hebert.  Cross-stitch networks for multi-task learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3994–4003, 2016.
  * Gao et al. [2019] Yuan Gao, Jiayi Ma, Mingbo Zhao, Wei Liu, and Alan L Yuille.  Nddr-cnn: Layerwise feature fusing in multi-task cnns by neural discriminative dimensionality reduction.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3205–3214, 2019.
  * Ruder et al. [2019] Sebastian Ruder, Joachim Bingel, Isabelle Augenstein, and Anders Søgaard.  Latent multi-task architecture learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2019.
  * Yang and Hospedales [2016a] Yongxin Yang and Timothy M Hospedales.  Trace norm regularised deep multi-task learning.  _arXiv preprint arXiv:1606.04038_ , 2016a.
  * Yang and Hospedales [2016b] Yongxin Yang and Timothy Hospedales.  Deep multi-task representation learning: A tensor factorisation approach.  _arXiv preprint arXiv:1605.06391_ , 2016b.
  * Rusu et al. [2016] Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell.  Progressive neural networks.  _arXiv preprint arXiv:1606.04671_ , 2016.
  * Long et al. [2015] Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Philip S Yu.  Learning multiple tasks with multilinear relationship networks.  _arXiv preprint arXiv:1506.02117_ , 2015.
  * Bhattacharjee et al. [2022] Deblina Bhattacharjee, Tong Zhang, Sabine Süsstrunk, and Mathieu Salzmann.  Mult: an end-to-end multitask learning transformer.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 12031–12041, 2022.
  * Kendall et al. [2018] Alex Kendall, Yarin Gal, and Roberto Cipolla.  Multi-task learning using uncertainty to weigh losses for scene geometry and semantics.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 7482–7491, 2018.
  * Lin et al. [2019] Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qing-Fu Zhang, and Sam Kwong.  Pareto multi-task learning.  _Advances in Neural Information Processing Systems_ , 32:12060–12070, 2019.
  * Caruana [1998] Rich Caruana.  _Multitask learning_.  Springer, 1998.
  * Teichmann et al. [2018] Marvin Teichmann, Michael Weber, Marius Zoellner, Roberto Cipolla, and Raquel Urtasun.  Multinet: Real-time joint semantic reasoning for autonomous driving.  In _2018 IEEE intelligent vehicles symposium (IV)_ , pages 1013–1020. IEEE, 2018.
  * Kokkinos [2017] Iasonas Kokkinos.  Ubernet: Training a universal convolutional neural network for low-, mid-, and high-level vision using diverse datasets and limited memory.  In _Proceedings of the IEE/CVFE Conference on Computer Vision and Pattern Recognition_ , pages 6129–6138, 2017.
  * Gao et al. [2020] Yuan Gao, Haoping Bai, Zequn Jie, Jiayi Ma, Kui Jia, and Wei Liu.  Mtl-nas: Task-agnostic neural architecture search towards general-purpose multi-task learning.  In _Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition_ , pages 11543–11552, 2020.
  * Vu et al. [2023] Thanh Vu, Yanqi Zhou, Chunfeng Wen, Yueqi Li, and Jan-Michael Frahm.  Toward edge-efficient dense predictions with synergistic multi-task neural architecture search.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pages 1400–1410, 2023.
  * Brüggemann et al. [2021] David Brüggemann, Menelaos Kanakis, Anton Obukhov, Stamatios Georgoulis, and Luc Van Gool.  Exploring relational context for multi-task dense prediction.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 15869–15878, 2021.
  * Guo et al. [2020] Pengsheng Guo, Chen-Yu Lee, and Daniel Ulbricht.  Learning to branch for multi-task learning.  In _International Conference on Machine Learning_ , 2020.
  * Sun et al. [2019] Ximeng Sun, Rameswar Panda, Rogerio Feris, and Kate Saenko.  Adashare: Learning what to share for efficient deep multi-task learning.  _arXiv preprint arXiv:1911.12423_ , 2019.
  * Vandenhende et al. [2019] Simon Vandenhende, Stamatios Georgoulis, Bert De Brabandere, and Luc Van Gool.  Branched multi-task networks: deciding what layers to share.  _arXiv preprint arXiv:1904.02920_ , 2019.
  * Standley et al. [2020] Trevor Standley, Amir Zamir, Dawn Chen, Leonidas Guibas, Jitendra Malik, and Silvio Savarese.  Which tasks should be learned together in multi-task learning?  In _International Conference on Machine Learning_ , pages 9120–9132. PMLR, 2020.
  * Bruggemann et al. [2020] David Bruggemann, Menelaos Kanakis, Stamatios Georgoulis, and Luc Van Gool.  Automated search for resource-efficient branched multi-task networks.  _arXiv preprint arXiv:2008.10292_ , 2020.
  * Navon et al. [2021] Aviv Navon, Aviv Shamsian, Gal Chechik, and Ethan Fetaya.  Learning the pareto front with hypernetworks.  In _International Conference on Learning Representations_ , 2021.
  * Yu and Huang [2019a] Jiahui Yu and Thomas S Huang.  Universally slimmable networks and improved training techniques.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 1803–1811, 2019a.
  * Yu and Huang [2019b] Jiahui Yu and Thomas Huang.  Autoslim: Towards one-shot architecture search for channel numbers.  _arXiv preprint arXiv:1903.11728_ , 2019b.
  * Hou et al. [2021] Liang Hou, Zehuan Yuan, Lei Huang, Huawei Shen, Xueqi Cheng, and Changhu Wang.  Slimmable generative adversarial networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 7746–7753, 2021.
  * Xue et al. [2022] Danna Xue, Fei Yang, Pei Wang, Luis Herranz, Jinqiu Sun, Yu Zhu, and Yanning Zhang.  Slimseg: Slimmable semantic segmentation with boundary supervision.  In _Proceedings of the 30th ACM International Conference on Multimedia_ , pages 6539–6548, 2022.
  * Li et al. [2021] Changlin Li, Guangrun Wang, Bing Wang, Xiaodan Liang, Zhihui Li, and Xiaojun Chang.  Dynamic slimmable network.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8607–8617, 2021.
  * Chin et al. [2021] Ting-Wu Chin, Ari S Morcos, and Diana Marculescu.  Joslim: J oint widths and weights o ptimization for slim mable neural networks.  In _Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13–17, 2021, Proceedings, Part III 21_ , pages 119–134. Springer, 2021.
  * Li and Bilen [2020] Wei-Hong Li and Hakan Bilen.  Knowledge distillation for multi-task learning.  In _Computer Vision–ECCV 2020 Workshops: Glasgow, UK, August 23–28, 2020, Proceedings, Part VI 16_ , pages 163–176. Springer, 2020.
  * Jacob et al. [2023] Geethu Miriam Jacob, Vishal Agarwal, and Björn Stenger.  Online knowledge distillation for multi-task learning.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pages 2359–2368, 2023.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32, 2019.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Zhong et al. [2020] Zhun Zhong, Liang Zheng, Guoliang Kang, Shaozi Li, and Yi Yang.  Random erasing data augmentation.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 34, pages 13001–13008, 2020.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pages 248–255. Ieee, 2009.
  * Fleischer [2003] Mark Fleischer.  The measure of pareto optima applications to multi-objective metaheuristics.  In _International Conference on Evolutionary Multi-Criterion Optimization_ , pages 519–533. Springer, 2003.
  * dee [2023] DeepSpeed.  https://github.com/microsoft/DeepSpeed, 2023.
  * Krizhevsky et al. [2009] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Rosenbaum et al. [2017] Clemens Rosenbaum, Tim Klinger, and Matthew Riemer.  Routing networks: Adaptive selection of non-linear functions for multi-task learning.  _arXiv preprint arXiv:1711.01239_ , 2017.
  * Chen et al. [2017] Liang-Chieh Chen, George Papandreou, Florian Schroff, and Hartwig Adam.  Rethinking atrous convolution for semantic image segmentation.  _arXiv preprint arXiv:1706.05587_ , 2017.
  * Sandler et al. [2018] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 4510–4520, 2018.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 770–778, 2016.
  * res [2018] Resnet9.  https://github.com/davidcpage/cifar10-fast, 2018.


remarkRemark hypothesisHypothesis claimClaim Parallel coarsening with
preserved spectraC. Brissette, A. Huang, and G. Slota

# Parallel coarsening of graph data with spectral guarantees††thanks: This
work is funded under Laboratory Directed Research and Development (LDRD)
program, Project No. 218474, at Sandia National Laboratories. Sandia National
Laboratories is a multimission laboratory managed and operated by National
Technology and Engineering Solutions of Sandia, LLC., a wholly owned
subsidiary of Honeywell International, Inc. for the U.S. Department of
Energy’s National Nuclear Security Administration under contract DE-
NA-0003525. This work was also supported by the U.S. Department of Energy,
Office of Science, under award DE-AC52-07NA27344 (FASTMath SciDAC Institute).
This paper describes objective technical results and analysis. Any subjective
views or opinions that might be expressed in the paper do not necessarily
represent the views of the U.S. Department of Energy or the United States
Government.

Christopher Brissette Rensselaer Polytechnic Intitute, Troy, NY ().
<EMAIL_ADDRESS>Andy Huang Sandia National Labs, Albuquerque, NM ().
<EMAIL_ADDRESS>George Slota Rensselaer Polytechnic Intitute, Troy, NY ().
<EMAIL_ADDRESS>
###### Abstract

Finding coarse representations of large graphs is an important computational
problem in the fields of scientific computing, large scale graph partitioning,
and the reduction of geometric meshes. Of particular interest in all of these
fields is the preservation of spectral properties with regards to the original
graph. While many methods exist to perform this task, they typically require
expensive linear algebraic operations and yield high work complexities. We
adapt a spectral coarsening bound from the literature in order to develop a
coarsening algorithm with a work complexity that is drastically smaller than
previous work. We further show that this algorithm is easily parallelizable
and presents impressive scaling results on meshes.

###### keywords:

spectral graph theory, graph coarsening, graph approximation, eigenvalues

05C22, 05C50, 68R10

##  1 Introduction

The coarsening of graphs while preserving properties of the original graph has
been widely studied in many contexts [2]. Starting with Gabriel Kron’s seminal
work coarsening resistor networks [9], the study has flourished to have uses
in computer graphics, multilevel partitioning, and broader network science
topics. While there are many different metrics one may preserve when
performing coarsening, in this work we focus on coarsening graphs so as to
preserve both the smallest eigenvalues and eigenvectors of the Laplacian of
the original graph. These techniques are particularly compelling given that
graph structures can be recovered from arbitrary data through constructions
such as the Vietoris Rips complex [14].
Several methods exist for performing the task of spectrum preserving
coarsening, however they are often computationally expensive. For instance in
Liu et al. [11] a method is suggested where an initial combinatorial
coarsening is performed and then cluster assignment is refined by iterating
upon and optimizing a given matrix norm. This method does not have an explicit
bound on its run time and instead iterates gradient descent to within some
tolerance. Alternatively, Loukas [12] suggests a “local variation” method
where $k$ eigenvalues are pre-computed and then used as a point of comparison
when considering potential merges. The explicit complexity of this method is
given by
$\tilde{O}(ckm+k^{2}n+ck^{3}+\sum_{l=1}^{c}\Phi_{l}(min\\{k^{2}\delta+k\delta^{2},k\delta^{2}+\delta^{3}\\}+log|\mathcal{F}_{l}|))$.
Here $c$ is the number of coarsening levels, $k$ is the number of desired
eigenvectors matched, $n$ is the number of nodes, and $m$ is the number of
edges in the original graph. For further details bout this complexity, one can
visit the original publication. Both of these methods boast powerful spectral
guarantees and impressive results. However, as discussed, they inherently have
limitations in terms of compute time due to both the usage of expensive linear
algebra operations as well as the methods being inherently sequential and
unable to make use of modern parallel architectures. Other spectrum preserving
coarsening methods [10, 1] fall victim to similar issues.
We will first define the notion of a coarsened graph. Note that we will assume
all graphs $G=(V,E)$ to be connected with no nodes of degree zero, the number
of nodes is $|V|=n$, the number of edges is $|E|=m$, and $n_{c}$ is the
desired number of nodes in our coarsening.

######  Definition 1.1.

Given a graph $G=(V,E)$, a coarsened graph $G_{c}=(V_{c},E_{c})$ is formed by
merging nodes in $\\{v_{1},\cdots,v_{k}\\}\subseteq V$ into super-nodes
$v_{c}\in V_{c}$. The associated edge weights for $v_{c}$ are given as
$a_{v_{c}x}=\sum_{v_{i}\in v_{c}}w_{v_{i}x}$.

Note that the Laplacian of $G$ has a higher dimension than the Laplacian of
its coarsened counterpart $G_{c}$. This makes comparing spectral properties
difficult. For this purpose we introduce the lift of a coarsened graph.
Intuitively this object takes a coarsened graph $G_{c}$ and projects it to the
same dimension as $G$. In doing so it provides us with a convenient way to
compare eigenvalues and eigenvectors of the original graph as well as the
coarsened graph.

######  Definition 1.2.

Given a coarsened graph $G_{c}=(V_{c},E_{c})$ of $G=(V,E)$, its lift
$\hat{G}=(\hat{V},\hat{E})$ is defined to be a graph on $n$ nodes, where every
super node in $V_{c}$ is expanded to its original number of nodes in $V$, and
the weight between each pair of nodes $u,v\in\hat{V}$ is
$\hat{w}(u,v)=\frac{\sum_{x\in u_{c}}\sum_{y\in
v_{c}}w(x,y)}{|u_{c}||v_{c}|}$. Here $u_{c},v_{c}\in V_{c}$ are the super
nodes that $u,v\in V$ belong to in the coarsened graph, and $|\cdot|$ denotes
the number of nodes within those super nodes. Additionally $w(a,b)$ is the
weight of the connection between nodes $a,b\in V$.

We interest ourselves with a bound presented by Jin and Loukas [7]. They
derive the following relationship between our original graph $G$, and its lift
$\hat{G}$ after coarsening.

######  Theorem 1.3.

For a graph $G=(V,E)$, if two nodes $u,v\in V$ are such that
$\|\frac{w_{u}}{d_{u}}-\frac{w_{v}}{d_{v}}\|_{1}\leq\epsilon$ and we merge
them, $\|\Lambda-\hat{\Lambda}\|_{\infty}\leq\epsilon$.

Here, $\Lambda$ is a sorted vector of eigenvalues of the normalized Laplacian
$\mathcal{L}(G)$ [3], $w_{x}$ is the weighted adjacency vector of node $x\in
V$, and $d_{x}$ is the degree of node $x\in V$ [5]. $\hat{\Lambda}$ is the
sorted vector of eigenvalues of the normalized Laplacian of the lift
$\mathcal{\hat{G}}$ after merging the nodes $u,v\in V$ in the original graph.
This bound is important since every eigenvalue of our coarsened graph is also
an eigenvalue of the lift [7].

##  2 A new algorithm

In [7] a greedy algorithm for spectrum consistent coarsening is defined. This
algorithm, which has a complexity of $O(m(n+n_{c})(n-n_{c}))$ will be called
the “explicit greedy algorithm” for the remainder of this paper. The algorithm
works as follows. For every edge in the graph the 1-norm is computed between
the adjacency vectors of the nodes at the ends of that edge. Then these
1-norms are sorted and a merge is performed along the edge with the smallest
1-norm. These steps are then repeated to our desired level of coarsening.
First we note how the inner two loops of the explicit greedy algorithm may be
parallelized. These loops iterate over each of $m$ edges and compute the
associated norm-difference between node adjacencies. Therefore we are
computing $O(m)$ norms, where the computation of each norm between nodes
$u,v\in V$ has sparse vector work complexity $O(d_{u}+d_{v})$. This gives us
an overall complexity for these inner loops of $O(n\left<d^{2}\right>)$ where
$\left<d^{2}\right>$ is the second moment of the degree distribution of our
graph. Note that none of these norms depend on previously computed norms, so
these inner loops can be parallelized such that given $p$ available threads,
if we evenly distribute the edges among threads we achieve a shared-memory
parallel-time complexity of $O(\frac{n}{p}\left<d^{2}\right>)$ for our inner
loops, where $p$ is the number of threads.
To achieve further complexity reduction we would like to be able to remove the
outer loop of the greedy algorithm. This will allow us to avoid recomputing
norm differences. For this purpose we make an additional observation that the
eigenvalue differences of an arbitrary level of coarsening may be bounded in
terms of the norm differences in the original uncoarsened graph given by the
following theorem.

######  Theorem 2.1.

Given a set of $s$ merges $\\{(a_{1},b_{1}),\cdots,(a_{s},b_{s})\\}$ where
$\|\frac{w_{a_{i}}}{d_{a_{i}}}-\frac{w_{b_{i}}}{d_{b_{i}}}\|_{1}\leq\epsilon$
for every $i\in[1..s]$, then we know
$\|\Lambda-\hat{\Lambda}\|_{\infty}\leq\frac{s(s+1)}{2}\epsilon$.

######  Proof 2.2.

The proof breaks in to two parts. First we wish to show that
$\|\frac{w_{a}}{d_{a}}-\frac{w_{b}}{d_{b}}\|_{1}\leq\epsilon$ implies, without
loss of generality, that
$\|\frac{w_{a}}{d_{a}}-\frac{w_{a}+w_{b}}{d_{a}+d_{b}}\|_{1}\leq epsilon$.
This statement says that if two nodes have a small adjacency difference norm
before merging, each of them will also have a small difference norm when
compared with the merged node. Take
$v=\frac{w_{a}}{d_{a}}-\frac{w_{a}+w_{b}}{d_{a}+d_{b}}$, then by algebra it
can be shown that
$\|v\|_{1}\leq\frac{\epsilon}{\frac{d_{a}}{d_{b}}+1}\leq\epsilon$, which
directly implies
$\|\frac{w_{a}}{d_{a}}-\frac{w_{a}+w_{b}}{d_{a}+d_{b}}\|_{1}\leq\epsilon$

For the second half of our proof, imagine we have performed some number of
merges. Then there are two possibilities for the subsequent merge. Either it
shares no nodes with the previous merge, or it shares nodes with the previous
merge. In the first case, neither of the nodes have been coarsened, so their
similarity remains the same and theorem 1.3 tells us that we simply add
$\epsilon$ to our spectral error bound after merging them. In the latter case,
assume without loss of generality that our merge consists of nodes $a,c$ where
$a$ overlaps with the first merge. Then by triangle inequality, and the first
part of our proof we know
$\|\frac{w_{c}}{d_{c}}-\frac{w_{a}+w_{b}}{d_{a}+d_{b}}\|_{1}\leq 2\epsilon$.
This means that the normalized adjacency vector of node $c$ is $2\epsilon$
similar to the normalized adjacency vector of the supernode given by our first
merge. Therefore we can apply Theorem 1.3 again and this error of $2\epsilon$,
adds to our bound. We may then repeat this process until our desired level of
coarsening, adding a factor of $\epsilon$ to each addition. The worst case
error occurs when all the merges overlap, in which case the upper bound is
given by the following.

$\displaystyle\|\Lambda-\hat{\Lambda}\|_{\infty}$
$\displaystyle\leq\sum_{k=1}^{s}k\epsilon=\frac{s(s+1)}{2}\epsilon$

While looser than the bound provided in [7], this bound requires no knowledge
about intermediate coarsenings of our graph. Because of this, we can remove
the outer loop of the explicit greedy algorithm to obtain an order $O(n)$ work
complexity reduction while still preserving a spectral bound. This gives us
our Algorithm 1.

Algorithm 1 Approximate Greedy Coarsen (G = (V,E), $n_{c}$, p)

$s\leftarrow|V|$

$\mathit{fitness}\leftarrow\emptyset$

$\\{E_{1},\cdots,E_{p}\\}\leftarrow\mathit{partition}(E,p)$

for $(a,b)\in E_{i}$ in parallel do

$\mathit{fitness}\leftarrow\mathit{fitness}\cup((a,b),\|\frac{w_{a}}{d_{a}}-\frac{w_{b}}{d_{b}}\|_{1})$

end for

$\mathit{fitness}\leftarrow\mathit{sort}(\mathit{fitness})$

while $s<n_{c}$ do

$(a,b)\leftarrow\mathit{fitness}[\mathit{index}][0]$

$G\leftarrow\mathit{merge}(a,b)$

$s\leftarrow s-1$

end while

Algorithm 1 closely resembles the explicit greedy algorithm with some
reorganization. We still iterate through every edge and calculate a fitness
function which is the norm-difference of the normalized adjacencies between
each node, however we only perform this once for each edge. Then a sort is
performed, which can be done in $O(\frac{m}{p}log(m))$ parallel time. Finally,
our merges are performed in order of fitness, requiring $O(n-n_{c})$
operations. This gives us a final parallel time of
$O(\frac{n}{p}\left<d^{2}\right>+\frac{m}{p}log(m)+(n-n_{c}))$ for Algorithm
1.

##  3 Results

We present results for both the scaling and approximation properties of our
algorithm on two small example graphs, the “Stanford bunny” from the Stanford
3D Scanning Repository111http://graphics.stanford.edu/data/3Dscanrep/ as well
as “ego-Facebook” from the Stanford Large Network Dataset
Collection222https://snap.stanford.edu/data/. The former is a nearly-regular
mesh and the latter has a highly irregular degree distribution. We find that
while spectral approximations appear better on the irregular “ego-Facebook”,
the parallel time scaling is far superior on the mesh.

###  3.1 Scaling

We observe in Figure 1 the runtime scaling of our algorithm for the “ego-
Facebook” and “Stanford bunny” graphs. We can see that, the Facebook graph has
drastically worse scaling properties which level out well before reaching the
final 2048 thread test. Additionally the Facebook graph requires far more time
to coarsen, despite it being almost a tenth the size of the bunny mesh. In
comparison, the bunny mesh experiences nearly theoretically ideal strong
scaling. This scaling difference can be attributed to load imbalance. Note
that in our parallel algorithm we do not parallelize within each norm
computation. For a highly irregular network such as “ego-Facebook” algorithm 1
partitions edges naively across threads without any consideration for the
nodes at either end of each edge. The irregularity of the degree distribution
in “ego-Facebook” guarantees that norm-differences along certain edges will
require far more compute time than others, and by not accounting for this it
is likely that some threads have significant work to perform when computing
norms, while others have little to compute. As an example, in the norm
computation step one thread may own $k$ edges which connect to the largest
degree node in the network with degree $D$, while another may own $k$ edges
that all connect to nodes with unit degree. In this case the latter thread
only has to complete $2k$ operations, while the former thread has to complete
more than $k(D+1)$ operations. This can be mitigated in future work through
more sophisticated thread parallelism and usage of more modern GPU
architectures, where warp divergence of threads is less of an issue [4].

Figure 1: Here we compare the scaling properties of our algorithm running from
32 to 2048 threads on a single Nvidia Quatro M5000 on each of the two test
graphs. We can see that the runtimes on the bunny mesh is incredibly small in
comparison with the Facebook graph, which has a highly irregular degree
distribution. Also notably, we observe that the bunny mesh almost reaches
theoretical perfect scaling.

###  3.2 Spectral approximation

In Figure 2 we present the eigenvector and eigenvalue approximation properties
for the “Stanford bunny” as well as “ego-Facebook” on the first fifty
nontrivial eigen-pairs. We compare the approximation properties on graphs
coarsened to half the number of nodes, quarter the number of nodes, and an
eighth the number of nodes. We can see that for both graphs, the half-
coarsening is a reasonably accurate approximation of the original eigenvalues,
however the eigenvalues quickly stray as we add additional levels of
coarsening. As for eigenvector approximations, we consider the inner product
between the first fifty normalized eigenvectors of the original graph with the
first fifty normalized eigenvectors of the lifted graph for each level of
coarsening. In Figure 2 eigenvector comparisons comprise the rightmost three
columns. The better the eigenvector approximation is, the more each matrix
will resemble an identity matrix since the eigenvectors of the normalized
Laplacian are orthogonal [3]. We see that the eigenvector approximation
appears better for “ego-Facebook” and for the “Stanford bunny” becomes rather
poor after half coarsening.
We also show example eigenvectors on the bunny graph and the lift of the half-
coarsened bunny graph in Figure 3. We can see that, while the positive and
negative regions drift for the selected eigenvectors, the overall pattern is
somewhat conserved. This is of significant interest since the sign patterns of
the eigenvectors are important for tasks such as spectral clustering [15].

Figure 2: We present spectral approximation properties on the two test-graphs.
Each graph was coarsened to half size, quarter size, and eighth size. On the
left we compare the first 50 eigenvalues of each lift against the eigenvalues
of the original graph. The right three columns compare the angles between the
associated eigenvectors by considering the dot product of the eigenvectors in
the original graph, with the eigenvectors of each lifted graph. Intuitively,
the closer this matrix resembles the identity, the better the eigenvector
approximation is.  Figure 3: Here we plot three eigenvectors on the original
bunny mesh as well as the corresponding lifted eigenvectors on the half-
coarsened bunny mesh. The A row are the eigenvectors on the original mesh, and
the B row contains the eigenvectors of the coarsened mesh. From left to right
the columns correspond to the Fiedler vector, the fifth, and the tenth
nontrivial eigenvectors respectively. The blue portions denote negative values
and red portions denote positive values. We can see that the eigenvector
values have drifted even though the eigenvalues are reasonably close as is
seen in Figure 2.

##  4 Conclusion and further work

In this paper we iterated upon a previously researched algorithm for
coarsening graphs while preserving approximate eigenvalues. This method can be
used to quickly compute spectrally approximate coarsenings of general graph
data such as geometric and finite element meshes. We presented a new bound for
the eigenvalue differences between original and coarsened graphs, and
presented a parallel algorithm for performing graph coarsening within this
bound. Our suggested algorithm has a parallel time of
$O(\frac{n}{p}\left<d^{2}\right>+\frac{m}{p}log(m)+(n-n_{c}))$ for coarsening
graph $G=(V,E)$ to $n_{c}$ nodes, a vast theoretical speed up over other
previously suggested coarsening algorithms preserving spectra. We additionally
showed that our algorithm remains faithful to the spectrum of the original
graph for limited amounts of coarsening, however the spectrum deviates
significantly as the number of nodes in the coarsening diminishes.
Our proposed coarsening algorithm leaves room for improvement in the areas of
accuracy and parallel time scaling. For the former, we observe that our Bound
2.1 is rather loose, and it may be tightened by recomputing difference-norms
between nodes after some amount of coarsening. This suggests that greater
overall accuracy may be obtainable by iterating the difference-norm
computations after some amount of coarsening. The optimal amount of coarsening
between such iterations remains an open problem. For parallel scaling, several
improvements could be made. As mentioned earlier in the manuscript, we
partition edges naively among threads which leads to load balancing issues for
irregular degree distributions. This could be remedied by considering more
sophisticated methods for partitioning the edge set, however this will likely
come at the cost of additional preemptive computations. Additionally, faster
norm-computations may be achieved by using finer-grained parallelism, where
multiple threads are assigned to compute each individual norm. Currently, each
norm is computed sequentially by a single thread, which leads to warp
divergence and compounds our imbalance issues. Well-known techniques such as
hierarchical parallelism [6], loop collapse [13], and graph adjacency
reordering [8] are relatively straightforward to implement and will greatly
improve speedups for irregular graph datasets.

## References

  * [1] H. Chen, H.-T. D. Liu, A. Jacobson, and D. I. Levin, Chordal decomposition for spectral coarsening, arXiv preprint arXiv:2009.02294, (2020).
  * [2] J. Chen, Y. Saad, and Z. Zhang, Graph coarsening: From scientific computing to machine learning, arXiv preprint arXiv:2106.11863, (2021).
  * [3] F. R. Chung and F. C. Graham, Spectral graph theory, no. 92, American Mathematical Soc., 1997.
  * [4] N. Coorporation, Nvidia tesla v100 gpu architecture, tech. report, Technical Report WP-08608. http://www. nvidia. com/object/volta-architecture …, 2017.
  * [5] C. Godsil and G. F. Royle, Algebraic graph theory, vol. 207, Springer Science & Business Media, 2001.
  * [6] S. Hong, S. K. Kim, T. Oguntebi, and K. Olukotun, Accelerating cuda graph algorithms at maximum warp, Acm Sigplan Notices, 46 (2011), pp. 267–276.
  * [7] Y. Jin, A. Loukas, and J. JaJa, Graph coarsening with preserved spectral properties, in International Conference on Artificial Intelligence and Statistics, PMLR, 2020, pp. 4452–4462.
  * [8] M. Kreutzer, G. Hager, G. Wellein, H. Fehske, and A. R. Bishop, A unified sparse matrix data format for efficient general sparse matrix-vector multiplication on modern processors with wide simd units, SIAM Journal on Scientific Computing, 36 (2014), pp. C401–C423.
  * [9] G. Kron, Tensor analysis of networks, New York, (1939).
  * [10] T. Lescoat, H.-T. D. Liu, J.-M. Thiery, A. Jacobson, T. Boubekeur, and M. Ovsjanikov, Spectral mesh simplification, in Computer Graphics Forum, vol. 39, Wiley Online Library, 2020, pp. 315–324.
  * [11] H.-T. D. LIU, A. JACOBSON, and M. OVSJANIKOV, Spectral coarsening of geometric operators, (2019).
  * [12] A. Loukas, Graph reduction with spectral and cut guarantees., J. Mach. Learn. Res., 20 (2019), pp. 1–42.
  * [13] G. M. Slota, S. Rajamanickam, and K. Madduri, High-performance graph analytics on manycore processors, in International Parallel & Distributed Processing Symposium (IPDPS), 2015.
  * [14] L. Vietoris, Über den höheren zusammenhang kompakter räume und eine klasse von zusammenhangstreuen abbildungen, Mathematische Annalen, 97 (1927), pp. 454–472.
  * [15] M. J. Zaki, W. Meira Jr, and W. Meira, Data mining and analysis: fundamental concepts and algorithms, Cambridge University Press, 2014.