# Efficient Pareto Manifold Learning with Low-Rank Structure

Weiyu Chen  James T. Kwok

###### Abstract

Multi-task learning, which optimizes performance across multiple tasks, is
inherently a multi-objective optimization problem. Various algorithms are
developed to provide discrete trade-off solutions on the Pareto front.
Recently, continuous Pareto front approximations using a linear combination of
base networks have emerged as a compelling strategy. However, it suffers from
scalability issues when the number of tasks is large. To address this issue,
we propose a novel approach that integrates a main network with several low-
rank matrices to efficiently learn the Pareto manifold. It significantly
reduces the number of parameters and facilitates the extraction of shared
features. We also introduce orthogonal regularization to further bolster
performance. Extensive experimental results demonstrate that the proposed
approach outperforms state-of-the-art baselines, especially on datasets with a
large number of tasks.

multi-objective optimization, multi-task learning

##  1 Introduction

Multi-task learning (MTL) (Caruana, 1997; Vandenhende et al., 2021) endeavors
to efficiently and effectively learn multiple tasks, leveraging shared
information to enhance overall performance. As tasks may have disparate scales
and potentially conflicting objectives, the challenge of balancing the tasks
is a critical aspect of MTL.

Building on the seminal work that conceptualizes MTL as a multi-objective
optimization (MOO) problem (Sener & Koltun, 2018), a suite of algorithms has
been developed to obtain trade-off solutions along the Pareto front (PF).
Examples include EPO (Mahapatra & Rajan, 2020), PMTL (Lin et al., 2019),
CAGrad (Liu et al., 2021a), and Nash-MTL (Navon et al., 2022). However, these
methods are limited to producing a finite set of discrete trade-off solutions,
lacking the flexibility to adapt to varying user preferences.

Continuous approximation of the PF aims to provide an arbitrary number of
solutions on the PF based on the user-provided preference vector. Pareto
hypernetwork-based methods (Navon et al., 2020b; Hoang et al., 2023) utilize a
hypernetwork (Ha et al., 2016) to learn the parameter space of a base network.
This hypernetwork accepts preference vector as input and outputs the
corresponding parameter of base network. Despite its efficacy, the size of the
hypernetwork significantly exceeds that of the base network, thus restricting
its use to small base networks. COSMOS (Ruchte & Grabocka, 2021) attempts to
circumvent this limitation by incorporating preference vectors directly into
the base network as an extra input. However, it falls short of achieving
satisfactory results due to the limited parameter space.

Pareto Manifold Learning (PaMaL) (Dimitriadis et al., 2023) proposes to find a
collection of base networks whose linear combination in the parameter space
based on the preference vectors yields the corresponding Pareto-optimal
solution. This approach exhibits promising performance. However, as we need to
maintain a separate base network for each task, it incurs a corresponding
surge in the number of parameters when we have a large number of tasks.
Moreover, base networks cannot learn from each other during training. This
lack of sharing poses challenges when the ensemble comprises a large number of
base networks.

To surmount these challenges, we introduce a novel approach that employs a
main network and multiple low-rank matrices, which can significantly reduce
the number of parameters when the number of tasks is large. Moreover, this
design facilitates the extraction of shared features through the main network
while simultaneously capturing task-specific differences via the low-rank
matrices. We further integrate orthogonal regularization to promote
disentanglement of these matrices. Empirical investigations demonstrate that
the proposed algorithm outperforms PaMaL and other baselines, particularly
when the number of tasks is large.

Notations. We denote the set $\\{1,\ldots,m\\}$ as $[m]$, and the
$m$-dimensional simplex
$\\{\bm{\alpha}\;|\;\sum_{i=1}^{m}\alpha_{i}=1,\alpha_{i}\geq 0\\}$ as
$\Delta^{m}$. The norm $\|\cdot\|$ refers to the Euclidean norm when applied
to vectors, and to the Frobenius norm when applied to matrices.

##  2 Background

###  2.1 Multi-Objective Optimization

A multi-objective optimization (MOO) (Miettinen, 1999) problem can be
formulated as

$\displaystyle\min_{\bm{\theta}\in\mathbb{R}^{d\times
k}}~{}~{}\bm{F}(\bm{\theta})$
$\displaystyle=[f_{1}(\bm{\theta}),\ldots,f_{m}(\bm{\theta})]^{\top},$ (1)

where $m\geq 2$ is the number of objectives, and $d\times k$ is the shape of
the parameter matrix. In this paper, we represent the parameters in matrix
form for convenience when discussing low-rank approximations.

######  Definition 2.1 (Pareto Dominance and Pareto-Optimal (Miettinen,
1999)).

A solution $\bm{\theta}_{1}$ is dominated by another solution
$\bm{\theta}_{2}$ if and only if $f_{i}(\bm{\theta}_{1})\geq
f_{i}(\bm{\theta}_{2})$ for $i\in[m]$, and $\exists
i\in[m],f_{i}(\bm{\theta}_{1})>f_{i}(\bm{\theta}_{2})$. A solution
$\bm{\theta}^{*}$ is Pareto-optimal if and only if it is not dominated by any
other $\bm{\theta}^{\prime}$.

A Pareto set (PS) is the set of all Pareto-optimal solutions. The Pareto front
(PF) refers to the functional values associated with the solutions in the PS.

###  2.2 Multi-Task Learning

Multi-task learning (MTL) (Caruana, 1997; Vandenhende et al., 2021) refers to
learning multiple tasks simultaneously. In this paper, we focus on the
optimization part, adopting the widely utilized shared-bottom architecture
(Caruana, 1997) as the base network. More specifically, for a $m$-task
network, we have a shared-bottom $\bm{\theta}^{sh}$ and $m$ task-specific
heads $\bm{\theta}^{t_{1}},\ldots,\bm{\theta}^{t_{m}}$. Throughout this paper,
our primary focus is on the shared-bottom $\bm{\theta}^{sh}$. Hence, any
mention of $\bm{\theta}$ hereafter refers specifically to $\bm{\theta}^{sh}$.

MTL can be viewed as a MOO problem (Sener & Koltun, 2018). To deal with the
possible conflicts of different tasks on the shared bottom, various algorithms
have been proposed, such as MGDA (Sener & Koltun, 2018; Désidéri, 2012),
PCGrad (Yu et al., 2020), IMTL (Liu et al., 2020), Graddrop (Chen et al.,
2020), RLW (Lin et al., 2022a), CAGrad (Liu et al., 2021a), Nash-MTL (Navon et
al., 2022), and Auto-$\lambda$ (Liu et al., 2022). These approaches, however,
predominantly focus on obtaining a single solution rather than capturing the
whole PF.

Discrete Approximation of Pareto Front. Lin et al. (2019) propose to generate
a set of solutions to approximate the Pareto front. Subsequent research have
introduced innovative strategies to enhance the discrete approximation.
Notable among these are EPO (Mahapatra & Rajan, 2020), MOO-SVGD (Liu et al.,
2021b), GMOOAR (Chen & Kwok, 2022) and PNG (Ye & Liu, 2022). These methods are
inherently limited to producing a fixed set of discrete points on the PF. Ma
et al. (2020) propose an algorithm to expand these discrete solutions in their
vicinity. However, it can only produce PF segments around each discrete
solution instead of the whole continuous PF.

Continuous Approximation of Pareto Front. Continuous approximation of PF
enables the derivation of solutions tailored to user preferences, offering an
arbitrary resolution of the trade-off solutions. Navon et al. (2020b)
introduces the concept of a Pareto hypernetwork (PHN), which learns a
hypernetwork (Ha et al., 2016) that takes a preference vector as input and
generates the corresponding Pareto-optimal network parameters. PHN-HVI (Hoang
et al., 2023) further develops the method using hypervolume maximization (Wang
et al., 2017). However, scalability of the approach becomes a concern when
applying the hypernetwork to large networks, as the size of the hypernetwork
is usually much larger than that of the base network itself.

Conditioned one-shot multi-objective search (COSMOS) (Ruchte & Grabocka, 2021)
incorporates the preference vector as an additional input, enabling the
generation of outputs with different preferences while minimizing the
introduction of extra parameters. Dosovitskiy & Djolonga (2019) propose the
use of FiLM layers (Perez et al., 2018) to incorporate preferences through
channel-wise multiplication and addition operations on the feature map.
However, these methods are sometimes constrained by the relatively limited
parameter space, which can lead to suboptimal performance.

Pareto manifold learning (PaMaL) (Dimitriadis et al., 2023) aims to jointly
learn multiple base networks $\bm{\theta}_{1},\ldots,\bm{\theta}_{m}$, such
that for any given preference vector $\bm{\alpha}\in\Delta^{m}$, the
corresponding weighted combination of base networks leads to the Pareto-
optimal model:

$\displaystyle\bm{\theta}(\bm{\alpha})=\sum_{i=1}^{m}\alpha_{i}\bm{\theta}_{i}.$
(2)

PaMaL demonstrates commendable performance. However, it only focuses on two or
three tasks. When dealing with a large number of tasks, the number of
parameters increases significantly as each task $i$ requires its own network
$\bm{\theta}_{i}$. Moreover, the base networks cannot benefit from each other
during training, which can potentially impair performance, especially when
scaling to a larger number of base networks.

Learning a continuous PF is also explored in Bayesian optimization (Lin et
al., 2022b) and evolutionary optimization (Lin et al., 2023) for engineering
problems with number of parameters up to 7. They fail to converge in deep
learning scenarios due to the significantly larger parameter spaces.

###  2.3 Low-Rank Adaptation

Low-rank adaptation (LoRA) has emerged as a popular approach in the field of
finetuning large pre-trained models (Hu et al., 2021). It only finetunes a
low-rank matrix instead of the entire model, resulting in improved efficiency
and the prevention of overfitting. Some subsequent studies (Ilharco et al.,
2022; Yadav et al., 2023; Ortiz-Jimenez et al., 2023) explore the merging of
LoRA modules trained on different tasks. These works focus on direct addition
or subtraction without incorporating any training. Audibert et al. (2023)
proposes fine-tuning a pretrained model for multiple tasks using a single LoRA
module (with some task-specific parameters). Wang et al. (2023a) proposes
fine-tuning a pretrained model by adding LoRA modules one by one, where the
newly-added LoRA module is orthogonal to the previous ones.

The main difference between these methods and the proposed method is that they
learn a single LoRA each time and output a single fine-tuned network, while we
train multiple low-rank matrices simultaneously and output a subspace of
networks. To mitigate dominance of unitary transforms in weight update as
observed in LoRA, Wang et al. (2023b) propose to split the LoRA module to
multiple LoRA modules. However, none of the existing research considers joint
training of an arbitrary convex combination of low-rank matrices to learn a
model subspace.

##  3 Proposed Method

In this section, we introduce a novel approach that involves learning a main
module and $m$ low-rank matrices for each layer (Section 3.1). Orthogonal
regularization is further introduced in Section 3.2. Finally, the whole
algorithm is presented in Section 3.3.

###  3.1 Low-Rank Structure

We start by examining the similarities of the base networks obtained by PaMaL
(Dimitriadis et al., 2023) on MultiMNIST (Sabour et al., 2017), using the same
experimental setting as PaMaL. Figure 2 shows the layer-wise cosine
similarities between two base networks’ parameters throughout training. As can
be seen, the similarities are almost zero at the beginning of training. As
training progresses, a marked increase in similarity is observed. Furthermore,
similarities are higher at the lower-level layers. This motivates us to
consider reducing the redundancy of base networks.

Consider the $m$ base networks in 2. Denote the parameters in the $l$th layer
of base network $\bm{\theta}_{i}$ by $\bm{\theta}_{i}^{l}$. In the $l$th
layer, 2 can be written as:

$\displaystyle\bm{\theta}(\bm{\alpha})^{l}=\sum_{i=1}^{m}\alpha_{i}\bm{\theta}_{i}^{l}.$
(3)

Let $\bm{\theta}_{0}^{l}=\frac{1}{m}\sum_{i=1}^{m}\bm{\theta}_{i}^{l}$. We can
rewrite 3 as:

$\displaystyle\bm{\theta}(\bm{\alpha})^{l}=\sum_{i=1}^{m}\alpha_{i}\left(\bm{\theta}_{0}^{l}+\frac{1}{m}\sum_{j=1}^{m}(\bm{\theta}_{i}^{l}-\bm{\theta}_{j}^{l})\right).$
(4)

Given the similarities observed from Figure 2, we approximate the difference
between any two modules $\bm{\theta}_{i}^{l}-\bm{\theta}_{j}^{l}$ by a low-
rank matrix. Then, we use the low-rank matrix $\bm{B}_{i}^{l}\bm{A}_{i}^{l}$,
to replace
$\frac{1}{m}\sum_{j=1}^{m}(\bm{\theta}_{i}^{l}-\bm{\theta}_{j}^{l})$ in 4,
leading to:

$\displaystyle\bm{\theta}(\bm{\alpha})^{l}=\sum_{i=1}^{m}\alpha_{i}(\bm{\theta}_{0}^{l}+\bm{B}_{i}^{l}\bm{A}_{i}^{l}).$
(5)

We further add a scaling factor $s$ to regulate the significance of the low-
rank component, as:

$\displaystyle\bm{\theta}(\bm{\alpha})^{l}=\bm{\theta}_{0}^{l}+s\sum_{i=1}^{m}\alpha_{i}\bm{B}_{i}^{l}\bm{A}_{i}^{l}.$
(6)

Through the above transformation, instead of learning $m$ base module in 3, we
learn a main module $\bm{\theta}_{0}^{l}$ and $m$ low-rank matrices
$\bm{B}_{1}^{l}\bm{A}_{1}^{l},\ldots,\bm{B}_{m}^{l}\bm{A}_{m}^{l}$. The main
modules are expected to capture the common features across multiple tasks,
thereby providing a shared foundation that each low-rank adaptation can
leverage. An illustrative example of the proposed method is shown in Figure 2.

Figure 1: Layer-wise similarities between base networks obtained by PaMaL on
MultiMNIST over three random seeds. Shaded areas represent the 95% confidence
interval.

Figure 2: Illustration of the proposed LORPMAN on a $L$-layer base network
with $m$ tasks. For each layer, we aim to learn $m$ low-rank matrices which
are orthogonal to each other.

####  3.1.1 Computational Efficiency

In the $l$th layer, let $\bm{B}_{i}^{l}\in\mathbb{R}^{d^{l}\times r^{l}}$ and
$\bm{A}_{i}^{l}\in\mathbb{R}^{r^{l}\times k^{l}}$. The proposed approach
reduces the number of parameters to only
$d^{l}k^{l}+m(d^{l}r^{l}+r^{l}k^{l})$. Notably, the rank $r^{l}$ is usually
set to be much smaller compared to $k^{l}$ and $d^{l}$. As a result, the
proposed method achieves higher parameter efficiency compared to PaMaL, which
has $md^{l}k^{l}$ parameters. This difference becomes more significant when
dealing with larger networks and a larger number of tasks.

####  3.1.2 Approximation Power

Similar to PaMaL (Dimitriadis et al., 2023), we show in this section the
approximation power of the proposed structure. While PaMaL only considers two
tasks, we consider the more general case with $m$ tasks. Denote the optimal
mapping from network input $\bm{x}\in X\subset\mathbb{R}^{u}$ and preference
vector $\bm{\alpha}\in\Delta^{m}$ to the corresponding point on the PF as
$t(\bm{x},\bm{\alpha}):X\times\Delta^{m}\rightarrow\mathbb{R}^{m}$. We have
the following Theorem.

######  Theorem 3.1.

Assume that $X\times\Delta^{m}$ is compact and $t(\bm{x},\bm{\alpha})$ is
continuous. For any $\epsilon>0$, there exists a ReLU MLP $h$ with main
network $\bm{\theta}_{0}$ and $m$ low-rank matrices
$\bm{B}_{1}\bm{A}_{1},\ldots,\bm{B}_{m}\bm{A}_{m}$, such that
$\forall\bm{x}\in X,\forall\bm{\alpha}\in\Delta^{m}$,

$\displaystyle\left\|t(\bm{x},\bm{\alpha})-h\left(\bm{x};\bm{\theta}_{0}+\sum_{i=1}^{m}\alpha_{i}\bm{B}_{i}\bm{A}_{i}\right)\right\|\leq\epsilon.$

The proof is in Appendix A. This Theorem shows that given any preference
vector $\bm{\alpha}$, the proposed main network with low-rank matrices can
approximately output the corresponding point on the PF within any given error
margin $\epsilon$.

###  3.2 Orthogonal Regularization

Orthogonal regularization, which encourages rows or columns of weight matrices
to be approximately orthogonal, has been employed in various scenarios to
regulate the parameters in a neural network (Xie et al., 2017; Bansal et al.,
2018; Wang et al., 2020). Here, we propose to extend it for orthogonality
among the low-rank matrices.

First, we flatten each low-rank matrix into a 1-dimensional vector and
normalize:
$\bm{w}^{l}_{i}=\frac{\texttt{flatten}(\bm{B}_{i}^{l}\bm{A}_{i}^{l})}{\left\|\texttt{flatten}(\bm{B}_{i}^{l}\bm{A}_{i}^{l})\right\|}$.
Next, we concatenate them to construct a $(d^{l}k^{l})\times m$ matrix
$\bm{W}^{l}=\texttt{concatenate}(\bm{w}^{l}_{1},\ldots,\bm{w}^{l}_{m})$. Our
objective is to encourage orthogonality among the matrix columns. This
orthogonality loss can be computed as:
$\mathcal{R}_{o}^{l}=\left\|(\bm{W}^{l})^{\top}\bm{W}^{l}-\bm{I}\right\|_{2}^{2}$,
where $\bm{I}$ is the $m\times m$ identity matrix. Finally, we compute the
loss for the entire network as:

$\displaystyle\mathcal{R}_{o}=\frac{1}{L}\sum_{l=1}^{L}\mathcal{R}_{o}^{l},$
(7)

where $L$ is the number of layers.

The objective of the orthogonal regularization is to reduce redundancy and
conflicts between different low-rank matrices. By reducing redundancy, the
model encourages learning common features in the main network and task-
specific features in the low-rank matrices, which can lead to more efficient
parameter usage and better performance.

Note that the computational complexity of the loss calculation is $O(m^{2})$,
which becomes expensive for large $m$. To address this, we use stochastic
approximation when $m$ exceeds 3. Specifically, in each iteration, a subset of
tasks $\mathcal{T}$, with cardinality 3, is randomly selected from the set of
all $m$ tasks. We then construct $\hat{\bm{W}}^{l}$ by concatenating
$\\{\bm{w}^{l}_{i}\\}_{i\in\mathcal{T}}$. Then, $\mathcal{R}_{o}^{l}$ is
estimated as:

$\displaystyle\mathcal{R}_{o}^{l}=\left\|(\hat{\bm{W}}^{l})^{\top}\hat{\bm{W}}^{l}-\bm{I}\right\|_{2}^{2},$
(8)

where $\bm{I}$ is the $3\times 3$ identity matrix.

This stochastic approximation ensures the complexity is independent of $m$.
Empirical evaluations in Section 4.3 demonstrate that this still maintains
satisfactory performance.

###  3.3 Optimization

To learn the Pareto manifold, we minimize the expectation of loss given an
$\bm{\alpha}$ over the Dirichlet distribution $Dir(\bm{p})$. The optimization
objective (without regularization) can be written as:

$\min_{\bm{\theta}_{0},\mathbf{B}_{1}\mathbf{A}_{1},\ldots,\mathbf{B}_{m}\mathbf{A}_{m}}\mathbb{E}_{\bm{\alpha}}\mathbb{E}_{\bm{\xi}}\left[\sum_{i=1}^{m}\alpha_{i}f_{i}(\bm{\theta}(\bm{\alpha});\bm{\xi})\right],$
(9)

where $\bm{\xi}$ is a mini-batch of multi-task training data
$\\{(x_{i}^{1},x_{i}^{2},\ldots,x_{i}^{m},y_{i}^{1},y_{i}^{2},\ldots,y_{i}^{m})\\}_{i=1}^{q}$
and $q$ is the batch size. For any given $\bm{\alpha}$, we aim to minimize
$\mathbb{E}_{\bm{\xi}}[\sum_{i=1}^{m}\alpha_{i}f_{i}(\bm{\theta}(\bm{\alpha});\bm{\xi})]$,
which is the linear scalarization of the $m$ objective functions. Note that
the solution obtained by linear scalarization is Pareto-optimal, which can be
formally stated as follows:

######  Proposition 3.2 ((Boyd & Vandenberghe, 2004)).

Given any $\bm{\alpha}\in\\{\bm{\alpha}~{}|~{}\alpha_{i}>0\\}$, the optimal
solution of the scalarized problem
$\min_{\bm{\theta}}\sum_{i=1}^{m}\alpha_{i}f_{i}(\bm{\theta})$ is a Pareto-
optimal solution of the original multi-objective optimization problem 1.

For the reader’s convenience, the proof is reproduced in Appendix B. Thus,
when 9 is minimized, the obtained $\bm{\theta}(\bm{\alpha})$’s are Pareto-
optimal solutions. Here, we only consider linear scalarization. More other
scalarization methods (Bowman Jr, 1975; Sener & Koltun, 2018; Navon et al.,
2022) can be considered.

The proposed algorithm, which is called LOw-Rank Pareto MANifold Learning
(LORPMAN), is shown in Algorithm 1. The training process is divided into two
phases: First, we adapt both the main model $\bm{\theta}_{0}$ and low-rank
matrices. After a certain number of epochs (which is referred to as freeze
epoch), we fix the main model and only adapt the low-rank matrices. This
encourages the low-rank matrices to learn task-specific representations
instead of always relying on the main model to improve performance.

In each iteration, we sample $b$ preference vectors
$\\{\bm{\alpha}^{1},\dots,\bm{\alpha}^{b}\\}$ from the Dirichlet distribution.
For each $\bm{\alpha}^{i}$, we compute the corresponding network parameters
according to 6. Then, following (Dimitriadis et al., 2023), we calculate the
multi-forward regularization loss $\mathcal{R}_{p}$ which penalizes incorrect
solution ordering on the PF (details in Appendix C). Subsequently, we
incorporate the orthogonal loss in 7 to encourage orthogonality among the
different low-rank matrices, as discussed in the previous section.

Algorithm 1 LORPMAN.

Input: learnable main model parameters $\bm{\theta}_{0}$, learnable matrix
$\\{\bm{A}_{i},\bm{B}_{i}\\}_{i=1}^{m}$, distribution parameters $\bm{p}$,
window size $b$, batch size $q$, regularization coefficients
$\lambda_{p},\lambda_{o}$, scaling parameter $s$.

while not converged do

sample a minibatch of multi-task training data
$\bm{\xi}=\\{(x_{i}^{1},x_{i}^{2},\ldots,x_{i}^{m},y_{i}^{1},y_{i}^{2},\ldots,y_{i}^{m})\\}_{i=1}^{q}$;

independently sample $\bm{\alpha}^{1},\ldots,\bm{\alpha}^{b}$ from
$\text{Dir}(\bm{p})$;

compute corresponding model parameter for each
$\bm{\alpha}^{j}$$\bm{\theta}(\bm{\alpha}^{j})^{l}=\bm{\theta}_{0}^{l}+s\sum_{i=1}^{m}\alpha_{i}^{j}\bm{B}_{i}^{l}\bm{A}_{i}^{l}$;

compute multi-forward regularization loss $\mathcal{R}_{p}$;

compute orthogonal loss $\mathcal{R}_{o}$ in Eq. (7);

compute loss
$\mathcal{L}=\sum_{j=1}^{b}\sum_{i=1}^{m}\alpha^{j}_{i}f_{i}(\bm{\theta}(\bm{\alpha}^{j});\bm{\xi})+\lambda_{p}\mathcal{R}_{p}+\lambda_{o}\mathcal{R}_{o}$;

if current epoch $<$ freeze epoch then

take a gradient descent step on $\bm{\theta}_{0}$ and
$\\{\bm{A}_{i},\bm{B}_{i}\\}_{i=1}^{m}$;

else

take a gradient descent step on $\\{\bm{A}_{i},\bm{B}_{i}\\}_{i=1}^{m}$;

end if

end while

##  4 Experiments

In this section, we first demonstrate the training process of the proposed
algorithm on a toy problem (Section 4.1). Then, we perform experiments on
datasets with two or three tasks (Section 4.2). Next, we scale up the number
of tasks to up to 40 (Section 4.3). We then compare the proposed method with
algorithms that generate discrete PFs (Section 4.4) and algorithms that can
generate a single solution (Section 4.5). Finally, ablation studies are
presented in Section 4.6.

We adopt the Hypervolume (HV) (Zitzler & Thiele, 1998; Knowles et al., 2003)
as performance indicator, which is widely used and can evaluate both the
convergence and diversity of the obtained PF. Details of the HV indicator are
in Section D.1. To evaluate the performance of the obtained PFs, following
(Dimitriadis et al., 2023), we sample 11 solutions on the obtained PF in the
two-objective cases, 66 solutions in the three-objective cases, and 100
solutions when there are more than three objectives. We tune the
hyperparameters according to the HV value on the validation datasets.

We compare the proposed method with state-of-the-art continuous PF
approximation algorithms, namely PHN (Navon et al., 2020b), PHN-HVI (Hoang et
al., 2023), COSMOS (Ruchte & Grabocka, 2021), and PaMaL (Dimitriadis et al.,
2023). Since PHN and PHN-HVI require training a hypernetwork with
significantly more parameters than the base network, they can only be run on
MultiMNIST and Census.

###  4.1 Illustrative Example

To demonstrate the training process of the proposed algorithm, we employ a
widely used two-objective toy problem (Yu et al., 2020; Liu et al., 2021a;
Navon et al., 2022), with parameter
$\bm{\theta}=[\theta^{1},\theta^{2}]\in\mathbb{R}^{2}$. The detailed
definition of the toy problem is in Section D.2.

We initialize $\bm{\theta}_{0}$ to $[4.5,4.5]$. Since the parameters of the
toy problem do not have a matrix structure, instead of using
$\bm{B}_{i}\bm{A}_{i}$s for low-rank approximation, we use
$\Delta\bm{\theta}_{i}\in\mathbb{R}^{2}$, where the second component is fixed
to mimic the low-rank approximation constraint. We initialize
$\Delta\bm{\theta}_{1}=[-4.5,0.0]$ and $\Delta\bm{\theta}_{2}=[4.5,0.0]$.
Given an $\bm{\alpha}$, the corresponding Pareto optimal parameter is
$\bm{\theta}(\bm{\alpha})=\bm{\theta}_{0}+\alpha_{1}\Delta\bm{\theta}_{1}+\alpha_{2}\Delta\bm{\theta}_{2}$.

Figure 3 shows the trajectories of $\bm{\theta}$ obtained by LORPMAN with
$\bm{\alpha}=[0.5,0.5]$, $[1,0]$, and $[0,1]$. We can see that $\bm{\theta}$
reaches the middle of the PF for $\bm{\alpha}=[0.5,0.5]$, and to the two
extreme points of the PF when $\bm{\alpha}=[1,0]$ and $[0,1]$. From Figure
3(b), we can see that these three solutions are on the same line in parameter
space and we can obtain the whole Pareto set by varying $\bm{\alpha}$.

(a) Objective space.

(b) Parameter space.

Figure 3: Trajectory of $\bm{\theta}$ obtained by LORPMAN with
$\bm{\alpha}=[0.5,0.5]$ (red), $\bm{\alpha}=[1,0]$ (green), and
$\bm{\alpha}=[0,1]$ (blue) in objective space (a) and parameter space (b).
Circles denote the initial points and squares denote the final points. The
gray lines in (a) and (b) denote the PF and PS, respectively.

###  4.2 Datasets with Two or Three Tasks

In this section, we examine the performance on datasets with two or three
tasks as used in (Dimitriadis et al., 2023), namely, MultiMNIST, Census, and
UTKFace.

(a) MultiMNIST.

(b) Census.

Figure 4: Test performance on MultiMNIST and Census. The PF is shown in bold. We show the results obtained by three different random seeds. Table 1: HV values obtained on MultiMNIST and Census (averaged over three random seeds). The standard deviation is shown in parentheses. For PHN and PHN-HVI, we report the number of parameters in the hypernetwork.  | MultiMNIST | Census
---|---|---
| HV | # Parameters | HV | # Parameters
PHN | 0.900 (0.0068) | 2.793M | 0.649 (0.0007) | 12.251M
PHN-HVI | 0.906 (0.0020) | 2.793M | 0.650 (0.0008) | 12.251M
COSMOS | 0.888 (0.0077) | 0.028M | 0.652 (0.0014) | 0.122M
PaMaL | 0.905 (0.0010) | 0.055M | 0.654 (0.0006) | 0.242M
LORPMAN | 0.918 (0.0018) | 0.046M | 0.656 (0.0004) | 0.133M

MultiMNIST and Census. MultiMNIST (Sabour et al., 2017) is a digit
classification dataset with two tasks: classification of the top-left digit
and classification of the bottom-right digit in each image. Census (Kohavi,
1996) is a tabular dataset with two tasks: age prediction and education level
classification.

Following (Dimitriadis et al., 2023), we use the LeNet111The parameters of a
convolution layer is a four-dimensional tensor instead of a matrix. We adopt
the approach in (Hu et al., 2021) to transform it into a matrix and perform
low-rank approximation. (LeCun et al., 1998) and Multilayer Perceptron (MLP)
as shared-bottom of the base network for MultiMNIST and Census, respectively.
For all algorithms, the number of training epochs is set to 10. For LORPMAN,
we choose the scaling factor $s\in\\{1,2,4,6\\}$ and freeze epoch
$\in\\{4,6,8\\}$ based on the validation set. For both datasets, the rank $r$
for all layers is set to 8 and the orthogonal regularization coefficient
$\lambda_{o}$ is set to 1. We do not tune $r$ and $\lambda_{o}$. More
experimental details on the two datasets are in Appendices D.3 and D.4,
respectively.

The resulting PFs are shown in Figure 4, and the corresponding HV values in
Table 1. As can be seen, LORPMAN can obtain the PF closer to the top-right
region (i.e., with better accuracies on both objectives). COSMOS exhibits
limited accuracies due to the constraints imposed by the small number of
parameters. Despite PaMaL, PHN, and PHN-HVI having a larger number of
parameters, they show inferior HVs when compared to LORPMAN.

UTKFace. UTKFace (Zhang et al., 2017) is a dataset with three tasks: age
prediction, gender classification and race classification. Following
(Dimitriadis et al., 2023), we use the ResNet-18 (He et al., 2016) as the
shared bottom of the base network. The number of training epochs is 100. We
tune $\lambda_{o}\in\\{0.1,0.5,1\\}$, freeze epoch $\in\\{60,80\\}$, and
$r\in\\{16,32,64\\}$. The scaling factor $s$ is set to 1 without tuning. More
experimental details are in Section D.5. We do not compare with PHN and PHN-
HVI because using the same hypernetwork structure as in MultiMNIST and Census
will result in a hypernetwork with approximately 1 billion parameters.

Table 2 shows the HVs obtained by COSMOS, PaMaL, and LORPMAN and the number of
parameters of each algorithm. As can be seen, LORPMAN outperforms PaMaL and
COSMOS, despite LORPMAN has fewer parameters than PaMaL. Figure 5 shows the
PFs obtained by PaMaL and LORPMAN.222Since the PF obtained by COSMOS is
inferior, it is omitted from the figure to maintain visual clarity. We can see
the solutions obtained by LORPMAN outperform PaMaL in all three objectives.

###  4.3 Scale to Large Number of Tasks

CIFAR-100. CIFAR-100 (Krizhevsky et al., 2009) is an image classification
dataset with 100 classes. These classes are further organized into 20
superclasses. As in (Rosenbaum et al., 2017; Yu et al., 2020; Liu et al.,
2022), we consider each superclass as a task. The objective of each task is to
accurately classify the image into one of the corresponding 5 more-specific
classes.

Following (Liu et al., 2022), we use VGG-16 (Simonyan & Zisserman, 2014) as
the base network. The number of training epochs is set to 300 and we freeze
the main model after 250 epochs, which is similar to the proportion in
UTKFace. The scaling factor $s$ is set to 1 without tuning. We search the
orthogonal regularization coefficient
$\lambda_{o}\in\\{0.001,0.005,0.01,0.1\\}$ and rank $r\in\\{8,16\\}$. More
experimental details are in Section D.6.

Table 2: HV values obtained on UTKFace (averaged over three random seeds). The standard deviation is shown in parentheses. | HV | # Parameters
---|---|---
COSMOS | 0.281 (0.003) | 11.2M
PaMaL | 0.304 (0.003) | 33.6M
LORPMAN | 0.314 (0.001) | 24.0M

(a)

(b)

(c)

(d)

Figure 5: Test performance of PaMaL and LORPMAN on UTKFace. Figures (b), (c),
(d) are 2D projections of (a) for better illustration of the 3D surface.

The obtained HVs are shown in Table 3. The obtained PFs are in Appendix E. The
results highlight the challenges encountered by PaMaL when dealing with a
large number of objectives. PaMaL needs to jointly train 20 base networks,
which leads to a large number of parameters and a small hypervolume. In
contrast, LORPMAN achieves significantly better hypervolume while utilizing
only 8.9% of the parameters compared to PaMaL. This underscores the efficiency
and effectiveness of LORPMAN in addressing problems with a large number of
tasks.

Table 3: HV values obtained on CIFAR-100 (averaged over three random seeds). The standard deviation is shown in parentheses.  | HV ($\times 10^{-2}$) | # Parameters
---|---|---
COSMOS | 0.344 (0.018) | 15.0M
PaMaL | 0.0583 (0.010) | 296.5M
LORPMAN | 0.887 (0.047) | 26.4M

Figure 6 shows the convergence of the training losses of PaMaL with different
learning rates. The training loss of LORPMAN (with learning rate $0.01$) is
also shown for comparison. We can observe that the poor performance of PaMaL
on CIFAR-100 is due to its slow convergence, since it has to jointly train 20
base networks. Simply increasing the learning rate does not help the
convergence of PaMaL.

Figure 6: Training loss of PaMaL with number of epochs, using different
learning rates.

CelebA. CelebA (Liu et al., 2015) is a face attribute classification dataset
with 40 tasks, where each task is a binary classification of a face attribute.
Following (Sener & Koltun, 2018), we use ResNet-18 (He et al., 2016) as the
base network. The number of training epochs is 50, and we freeze the main
model after 40 epochs, which is similar to the proportion in UTKFace. The
scaling factor $s$ is set to 1 without tuning. We search the orthogonal
regularization coefficient $\lambda_{o}\in\\{0.1,0.5,1\\}$ and rank
$r\in\\{8,16,32\\}$. Here, we consider two more baselines: (i) PHN with
chunking (Navon et al., 2020a; Lin et al., 2020), both with the original
setting in (Navon et al., 2020a) (i.e, the hidden dimension is set to 100) and
a scaled setting with comparable number of parameters as LORPMAN (i.e., the
hidden dimension is set to 500); and (ii) FiLM condition, with a FiLM
condition layer added after each block of ResNet-18. More experimental details
are described in Section D.7.

The HV values are shown in Table 4. We can see that LORPMAN achieves much
better performance while using only 21% of parameters compared to PaMaL. The
FiLM condition suffers similar problems as COSMOS due to the limited number of
parameters. PHN with chunking also shows worse performance than LORPMAN. In
comparison, the proposed LORPMAN is a more straightforward approach that
achieves good performance and parameter efficiency.

Table 4: HV values obtained on CelebA (averaged over three random seeds). The standard deviation is shown in parentheses.  Method | HV ($\times 10^{-2}$) | # Parameters
---|---|---
PHN-Chunking (original) | 0.663 (0.027) | 36.6M
PHN-Chunking (scaled) | 0.681 (0.048) | 92.3M
FiLM | 0.803 (0.022) | 11.4M
COSMOS | 0.783 (0.013) | 11.4M
PaMaL | 0.472 (0.018) | 453.3M
LORPMAN | 1.167 (0.008) | 96.8M

###  4.4 Comparison with Discrete PF Baselines

In this experiment, we compare with five algorithms that obtain discrete PFs:
EPO (Mahapatra & Rajan, 2020), PMTL (Lin et al., 2019), MOO-SVGD (Liu et al.,
2021b), PNG (Ye & Liu, 2022), and GMOOAR (Chen & Kwok, 2022). Since most of
these algorithms have performed experiments on MultiMNIST, we use MultiMNIST
for comparison. The settings are the same as in Section 4.2.

The obtained solutions are shown in Figure 7. As can be seen, the proposed
algorithm has better performance than existing discrete PF algorithms, even
though they can only generate a predetermined number of solutions.

Figure 7: Test performance of LORPMAN and various discrete PF algorithms on
MultiMNIST.

###  4.5 Comparison with Single-Solution Baselines

In this experiment, we compare with multi-task learning baselines that can
only generate a single solution. These include Linear Scalarization (LS), UW
(Kendall et al., 2018), MGDA (Sener & Koltun, 2018), DWA (Liu et al., 2019),
PCGrad (Yu et al., 2020), IMTL (Liu et al., 2020), Graddrop (Chen et al.,
2020), CAGrad (Liu et al., 2021a), RLW (Lin et al., 2022a), Nash-MTL (Navon et
al., 2022), RotoGrad (Javaloy & Valera, 2021), and Auto-$\lambda$ (Liu et al.,
2022). For a more complete comparison, we also include the results obtained by
Single-Task Learning (STL), where each task is trained independently, and the
baselines of COSMOS and PaMaL which provide continuous approximations of the
PF.

Following (Dimitriadis et al., 2023), we use a widely-used dataset CityScapes
(Cordts et al., 2016). It is a scene-understanding dataset with two tasks:
semantic segmentation and depth regression. We adopt the SegNet
(Badrinarayanan et al., 2017) as the base network and use the same parameter
configuration as in (Dimitriadis et al., 2023). The number of training epochs
is 100. We tune freeze epoch $\in\\{80,90\\}$, $s\in\\{0.5,1\\}$, and
$r\in\\{32,64\\}$. More experimental details are in Section D.8.

LORPMAN/COSMOS/PaMaL can provide the whole PF. We only select one solution
from their obtained PFs for comparison with the single-solution algorithms.
Table 5 shows the performance on semantic segmentation (mIOU and pixel
accuracy) and depth prediction (absolute and relative error) on the test set.
We can see that LORPMAN not only surpasses COSMOS and PaMaL but also
outperforms the single-solution algorithms. While MGDA achieves slightly
better relative error in depth estimation, it has much worse performance in
the semantic segmentation task.

It is important to note that our objective is to learn the entire PF rather
than focusing on a single solution.

Table 5: Test performance on CityScapes. We show the average over three random
seeds. Results, excluding LORPMAN, are taken from (Dimitriadis et al., 2023)

.  Segmentation Depth mIoU $\uparrow$ Pix Acc $\uparrow$ Abs Err $\downarrow$
Rel Err $\downarrow$ STL 70.96 92.12 0.0141 38.644 LS 70.12 91.90 0.0192
124.061 UW 70.20 91.93 0.0189 125.943 MGDA 66.45 90.79 0.0141 53.138 DWA 70.10
91.89 0.0192 127.659 PCGrad 70.02 91.84 0.0188 126.255 IMTL 70.77 92.12 0.0151
74.230 Graddrop 70.07 91.93 0.0189 127.146 CAGrad 69.23 91.61 0.0168 110.139
RLW 68.79 91.52 0.0213 126.942 Nash-MTL 71.13 92.23 0.0157 78.499 RotoGrad
69.92 91.85 0.0193 127.281 Auto-$\lambda$ 70.47 92.01 0.0177 116.959 COSMOS
69.78 91.79 0.0539 136.614 PaMaL 70.35 91.99 0.0141 54.520 LORPMAN 72.13 92.57
0.0135 54.942

###  4.6 Ablation Studies

In this section, we investigate the effects of (i) orthogonal regularization,
(ii) rank $r$, (iii) freeze epoch, and (iv) scaling factor $s$ on the
performance of LORPMAN. Experiment is performed on the UTKFace dataset.

Orthogonal Regularization. Table 6 shows the impact of orthogonal
regularization on HV and the average correlation333The correlation between a
pair of low-rank matrices $\mathbf{B}_{i}\mathbf{A}_{i}$ and
$\mathbf{B}_{j}\mathbf{A}_{j}$ is computed as
$\texttt{flatten}(\mathbf{B}_{i}\mathbf{A}_{i})^{\top}\texttt{flatten}(\mathbf{B}_{j}\mathbf{A}_{j})/(\left\|\mathbf{B}_{i}\mathbf{A}_{i}\right\|\left\|\mathbf{B}_{j}\mathbf{A}_{j}\right\|)$.
over all pairs of low-rank matrices. We can see that with orthogonal
regularization, the correlation between low-rank matrices is significantly
reduced. Similar observations can also be found in traditional orthogonal
regularization for parameters within a single neural network (Xie et al.,
2017; Bansal et al., 2018). Such reduction in correlation encourages learning
common features in the main network and differences in the low-rank matrices,
thus leading to better HV value.

Table 6: Effects of orthogonal regularization on UTKFace (averaged over six random seeds). | HV | Correlation
---|---|---
w/o orthogonal reg | 0.309 (0.002) | 0.466 (0.045)
w/ orthogonal reg | 0.314 (0.001) | 0.067 (0.012)

Rank $r$. Table 7 shows the effects of the rank $r$ on the HV and number of
parameters. We can observe that LORPMAN with a rank $8$ can already outperform
COSMOS and PaMaL (see Table 2). By increasing the rank to 64, even better
performance can be achieved. However, further increasing the rank does not
yield significant change.

Table 7: Effects of rank $r$ on UTKFace (averaged over six random seeds). $r$ | HV | # parameters
---|---|---
4 | 0.306 (0.002) | 12.1M
8 | 0.310 (0.001) | 12.8M
16 | 0.310 (0.002) | 14.5M
32 | 0.311 (0.001) | 17.6M
64 | 0.314 (0.001) | 24.0M
128 | 0.313 (0.002) | 35.5M

Freeze Epoch. Table 9 shows the effect of freeze epoch on HV. Compared with
not freezing the main module (i.e., freeze epoch = 100), freezing during the
latter half of the training process encourages the low-rank matrices to learn
task-specific representations instead of always relying on the main model,
thus leading to better performance.

Scaling Factor $s$. Table 9 shows the effect of scaling factor $s$ on HV. As
can be seen, setting $s$ within a reasonable range (such as $[0.1,1]$) leads
to stable performance.

Table 8: Effects of freeze epoch on UTKFace (averaged over six random seeds). freeze | HV
---|---
20 | 0.305 (0.001)
40 | 0.311 (0.001)
60 | 0.312 (0.002)
80 | 0.314 (0.001)
100 | 0.307 (0.003)

Table 9: Effects of scaling factor $s$ on UTKFace (averaged over six random seeds). $s$ | HV
---|---
0.1 | 0.313 (0.001)
0.5 | 0.313 (0.001)
1 | 0.314 (0.001)
1.5 | 0.312 (0.002)
2 | 0.310 (0.002)

##  5 Conclusion

In this paper, we introduce a novel method for continuous approximation of the
PF. We use a main network with a collection of low-rank matrices. Our approach
leverages the inherent structure of Pareto manifold to effectively learn
trade-off solutions between tasks. Extensive empirical evaluation on various
datasets demonstrates the superior performance of the proposed algorithm,
especially when the number of tasks is large.

One limitation of the proposed work is that we consider the same rank for all
layers. Using different ranks for different layers to achieve better parameter
efficiency and exploring automatic rank setting strategies could be
interesting future directions.

## Acknowledgements

This research was supported in part by the Research Grants Council of the Hong
Kong Special Administrative Region (Grant 16202523).

## Impact Statement

The proposed algorithm can effectively discover trade-off solutions among
multiple tasks, leading to improved performance and cost efficiency in real-
world applications involving multiple objectives. However, we should be aware
the potential biases and privacy concerns when processing data from different
tasks.

## References

  * Audibert et al. (2023) Audibert, A., Amini, M. R., Usevich, K., and Clausel, M.  Low-rank updates of pre-trained weights for multi-task learning.  In _Findings of the Association for Computational Linguistics_ , pp. 7544–7554, 2023.
  * Badrinarayanan et al. (2017) Badrinarayanan, V., Kendall, A., and Cipolla, R.  Segnet: A deep convolutional encoder-decoder architecture for image segmentation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 39(12):2481–2495, 2017.
  * Bansal et al. (2018) Bansal, N., Chen, X., and Wang, Z.  Can we gain more from orthogonality regularizations in training deep networks?  In _Neural Information Processing Systems_ , 2018.
  * Bowman Jr (1975) Bowman Jr, V. J.  On the relationship of the Tchebycheff norm and the efficient frontier of multiple-criteria objectives.  In _Multiple Criteria Decision Making: Proceedings of a Conference Jouy-en-Josas_ , pp. 76–86. Springer, 1975.
  * Boyd & Vandenberghe (2004) Boyd, S. P. and Vandenberghe, L.  _Convex Optimization_.  Cambridge University Press, 2004.
  * Caruana (1997) Caruana, R.  Multitask learning.  _Machine Learning_ , 28:41–75, 1997.
  * Chen & Kwok (2022) Chen, W. and Kwok, J.  Multi-objective deep learning with adaptive reference vectors.  In _Neural Information Processing Systems_ , pp. 32723–32735, 2022.
  * Chen et al. (2020) Chen, Z., Ngiam, J., Huang, Y., Luong, T., Kretzschmar, H., Chai, Y., and Anguelov, D.  Just pick a sign: Optimizing deep multitask models with gradient sign dropout.  In _Neural Information Processing Systems_ , pp. 2039–2050, 2020.
  * Cordts et al. (2016) Cordts, M., Omran, M., Ramos, S., Rehfeld, T., Enzweiler, M., Benenson, R., Franke, U., Roth, S., and Schiele, B.  The cityscapes dataset for semantic urban scene understanding.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 3213–3223, 2016.
  * Désidéri (2012) Désidéri, J.-A.  Multiple-gradient descent algorithm (MGDA) for multiobjective optimization.  _Comptes Rendus Mathematique_ , 350(5-6):313–318, 2012.
  * Dimitriadis et al. (2023) Dimitriadis, N., Frossard, P., and Fleuret, F.  Pareto manifold learning: Tackling multiple tasks via ensembles of single-task models.  In _International Conference on Machine Learning_ , pp. 8015–8052, 2023.
  * Dosovitskiy & Djolonga (2019) Dosovitskiy, A. and Djolonga, J.  You only train once: Loss-conditional training of deep networks.  In _International Conference on Learning Representations_ , 2019.
  * Ha et al. (2016) Ha, D., Dai, A., and Le, Q. V.  Hypernetworks.  Preprint arXiv:1609.09106, 2016.
  * Haykin (1998) Haykin, S.  _Neural Networks: A Comprehensive Foundation_.  Prentice Hall, 1998.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 770–778, 2016.
  * Hoang et al. (2023) Hoang, L. P., Le, D. D., Tuan, T. A., and Thang, T. N.  Improving Pareto front learning via multi-sample hypernetworks.  In _AAAI Conference on Artificial Intelligence_ , pp. 7875–7883, 2023.
  * Hu et al. (2021) Hu, E. J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., and Chen, W.  LoRA: Low-rank adaptation of large language models.  Preprint arXiv:2106.09685, 2021.
  * Huber (1992) Huber, P. J.  Robust estimation of a location parameter.  In _Breakthroughs in Statistics: Methodology and Distribution_ , pp. 492–518. Springer, 1992.
  * Ilharco et al. (2022) Ilharco, G., Ribeiro, M. T., Wortsman, M., Schmidt, L., Hajishirzi, H., and Farhadi, A.  Editing models with task arithmetic.  In _International Conference on Learning Representations_ , 2022.
  * Javaloy & Valera (2021) Javaloy, A. and Valera, I.  Rotograd: Gradient homogenization in multitask learning.  Preprint arXiv:2103.02631, 2021.
  * Kendall et al. (2018) Kendall, A., Gal, Y., and Cipolla, R.  Multi-task learning using uncertainty to weigh losses for scene geometry and semantics.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 7482–7491, 2018.
  * Knowles et al. (2003) Knowles, J. D., Corne, D. W., and Fleischer, M.  Bounded archiving using the Lebesgue measure.  In _Congress on Evolutionary Computation_ , pp. 2490–2497, 2003.
  * Kohavi (1996) Kohavi, R.  Scaling up the accuracy of naive-Bayes classifiers: A decision-tree hybrid.  In _International Conference on Knowledge Discovery and Data Mining_ , pp. 202–207, 1996.
  * Krizhevsky et al. (2009) Krizhevsky, A., Hinton, G., et al.  Learning multiple layers of features from tiny images.  Technical report, University of Toronto, 2009.
  * Kurin et al. (2022) Kurin, V., De Palma, A., Kostrikov, I., Whiteson, S., and Mudigonda, P. K.  In defense of the unitary scalarization for deep multi-task learning.  In _Neural Information Processing Systems_ , pp. 12169–12183, 2022.
  * LeCun et al. (1998) LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Lin et al. (2022a) Lin, B., Feiyang, Y., Zhang, Y., and Tsang, I.  Reasonable effectiveness of random weighting: A litmus test for multi-task learning.  _Transactions on Machine Learning Research_ , 2022a.
  * Lin et al. (2019) Lin, X., Zhen, H.-L., Li, Z., Zhang, Q.-F., and Kwong, S.  Pareto multi-task learning.  In _Neural Information Processing Systems_ , 2019.
  * Lin et al. (2020) Lin, X., Yang, Z., Zhang, Q., and Kwong, S.  Controllable Pareto multi-task learning.  Preprint arXiv preprint arXiv:2010.06313, 2020.
  * Lin et al. (2022b) Lin, X., Yang, Z., Zhang, X., and Zhang, Q.  Pareto set learning for expensive multi-objective optimization.  pp. 19231–19247, 2022b.
  * Lin et al. (2023) Lin, X., Zhang, X., Yang, Z., and Zhang, Q.  Evolutionary Pareto set learning with structure constraints.  Preprint arXiv:2310.20426, 2023.
  * Liu et al. (2021a) Liu, B., Liu, X., Jin, X., Stone, P., and Liu, Q.  Conflict-averse gradient descent for multi-task learning.  In _Neural Information Processing Systems_ , pp. 18878–18890, 2021a.
  * Liu et al. (2020) Liu, L., Li, Y., Kuang, Z., Xue, J.-H., Chen, Y., Yang, W., Liao, Q., and Zhang, W.  Towards impartial multi-task learning.  In _International Conference on Learning Representations_ , 2020.
  * Liu et al. (2019) Liu, S., Johns, E., and Davison, A. J.  End-to-end multi-task learning with attention.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 1871–1880, 2019.
  * Liu et al. (2022) Liu, S., James, S., Davison, A., and Johns, E.  Auto-Lambda: Disentangling dynamic task relationships.  _Transactions on Machine Learning Research_ , 2022.
  * Liu et al. (2021b) Liu, X., Tong, X., and Liu, Q.  Profiling Pareto front with multi-objective stein variational gradient descent.  In _Neural Information Processing Systems_ , pp. 14721–14733, 2021b.
  * Liu et al. (2015) Liu, Z., Luo, P., Wang, X., and Tang, X.  Deep learning face attributes in the wild.  In _International Conference on Computer Vision_ , 2015.
  * Ma et al. (2020) Ma, P., Du, T., and Matusik, W.  Efficient continuous Pareto exploration in multi-task learning.  In _International Conference on Machine Learning_ , pp. 6522–6531, 2020.
  * Mahapatra & Rajan (2020) Mahapatra, D. and Rajan, V.  Multi-task learning with user preferences: Gradient descent with controlled ascent in Pareto optimization.  In _International Conference on Machine Learning_ , pp. 6597–6607, 2020.
  * Miettinen (1999) Miettinen, K.  _Nonlinear Multiobjective Optimization_ , volume 12.  Springer Science & Business Media, 1999.
  * Navon et al. (2020a) Navon, A., Shamsian, A., Chechik, G., and Fetaya, E.  Learning the Pareto front with hypernetworks.  Preprint arXiv:2010.04104, 2020a.
  * Navon et al. (2020b) Navon, A., Shamsian, A., Fetaya, E., and Chechik, G.  Learning the Pareto front with hypernetworks.  In _International Conference on Learning Representations_ , 2020b.
  * Navon et al. (2022) Navon, A., Shamsian, A., Achituve, I., Maron, H., Kawaguchi, K., Chechik, G., and Fetaya, E.  Multi-task learning as a bargaining game.  In _International Conference on Machine Learning_ , pp. 16428–16446, 2022.
  * Ortiz-Jimenez et al. (2023) Ortiz-Jimenez, G., Favero, A., and Frossard, P.  Task arithmetic in the tangent space: Improved editing of pre-trained models.  Preprint arXiv:2305.12827, 2023.
  * Perez et al. (2018) Perez, E., Strub, F., De Vries, H., Dumoulin, V., and Courville, A.  FiLM: Visual reasoning with a general conditioning layer.  In _AAAI Conference on Artificial Intelligence_ , 2018.
  * Rosenbaum et al. (2017) Rosenbaum, C., Klinger, T., and Riemer, M.  Routing networks: Adaptive selection of non-linear functions for multi-task learning.  Preprint arXiv:1711.01239, 2017.
  * Ruchte & Grabocka (2021) Ruchte, M. and Grabocka, J.  Scalable Pareto front approximation for deep multi-objective learning.  In _IEEE International Conference on Data Mining_ , pp. 1306–1311, 2021.
  * Sabour et al. (2017) Sabour, S., Frosst, N., and Hinton, G. E.  Dynamic routing between capsules.  In _Neural Information Processing Systems_ , 2017.
  * Sener & Koltun (2018) Sener, O. and Koltun, V.  Multi-task learning as multi-objective optimization.  In _Neural Information Processing Systems_ , 2018.
  * Simonyan & Zisserman (2014) Simonyan, K. and Zisserman, A.  Very deep convolutional networks for large-scale image recognition.  Preprint arXiv:1409.1556, 2014.
  * Vandenhende et al. (2021) Vandenhende, S., Georgoulis, S., Van Gansbeke, W., Proesmans, M., Dai, D., and Van Gool, L.  Multi-task learning for dense prediction tasks: A survey.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 44(7):3614–3633, 2021.
  * Wang et al. (2017) Wang, H., Deutz, A., Bäck, T., and Emmerich, M.  Hypervolume indicator gradient ascent multi-objective optimization.  In _International Conference on Evolutionary Multi-Criterion Optimization_ , pp. 654–669, 2017.
  * Wang et al. (2020) Wang, J., Chen, Y., Chakraborty, R., and Yu, S. X.  Orthogonal convolutional neural networks.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 11505–11515, 2020.
  * Wang et al. (2023a) Wang, X., Chen, T., Ge, Q., Xia, H., Bao, R., Zheng, R., Zhang, Q., Gui, T., and Huang, X.-J.  Orthogonal subspace learning for language model continual learning.  In _Findings of the Association for Computational Linguistics_ , pp. 10658–10671, 2023a.
  * Wang et al. (2023b) Wang, Y., Lin, Y., Zeng, X., and Zhang, G.  MultiLoRA: Democratizing LoRA for better multi-task learning.  Preprint arXiv:2311.11501, 2023b.
  * Xie et al. (2017) Xie, D., Xiong, J., and Pu, S.  All you need is beyond a good init: Exploring better solution for training extremely deep convolutional neural networks with orthonormality and modulation.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 6176–6185, 2017.
  * Yadav et al. (2023) Yadav, P., Tam, D., Choshen, L., Raffel, C., and Bansal, M.  TIES-merging: Resolving interference when merging models.  In _Neural Information Processing Systems_ , 2023.
  * Ye & Liu (2022) Ye, M. and Liu, Q.  Pareto navigation gradient descent: A first-order algorithm for optimization in Pareto set.  In _Uncertainty in Artificial Intelligence_ , pp. 2246–2255, 2022.
  * Yu et al. (2020) Yu, T., Kumar, S., Gupta, A., Levine, S., Hausman, K., and Finn, C.  Gradient surgery for multi-task learning.  In _Neural Information Processing Systems_ , pp. 5824–5836, 2020.
  * Zhang et al. (2017) Zhang, Z., Song, Y., and Qi, H.  Age progression/regression by conditional adversarial autoencoder.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 5810–5818, 2017.
  * Zitzler & Thiele (1998) Zitzler, E. and Thiele, L.  Multiobjective optimization using evolutionary algorithms — A comparative case study.  In _International Conference on Parallel Problem Solving from Nature_ , pp. 292–301, 1998.

##  Appendix A Proof of Theorem 3.1

Denote the optimal mapping from network input $\bm{x}\in
X\subset\mathbb{R}^{u}$ and preference vector $\bm{\alpha}\in\Delta^{m}$ to
the corresponding point on the PF as
$t(\bm{x},\bm{\alpha}):X\times\Delta^{m}\rightarrow\mathbb{R}^{m}$. We have
the following Theorem.

######  Theorem A.1.

Assume that $X\times\Delta^{m}$ is compact and $t(\bm{x},\bm{\alpha})$ is
continuous. For any $\epsilon>0$, there exists a ReLU MLP $h$ with main
network $\bm{\theta}_{0}$ and $m$ low-rank matrices
$\bm{B}_{1}\bm{A}_{1},\ldots,\bm{B}_{m}\bm{A}_{m}$, such that
$\forall\bm{x}\in X,\forall\bm{\alpha}\in\Delta^{m}$,

$\displaystyle\left\|t(\bm{x},\bm{\alpha})-h\left(\bm{x};\bm{\theta}_{0}+\sum_{i=1}^{m}\alpha_{i}\bm{B}_{i}\bm{A}_{i}\right)\right\|\leq\epsilon.$

###### Proof.

Denote $\sigma(\bm{x})\equiv\max(\bm{0},\bm{x})$. From the universal
approximation theorem (Haykin, 1998), for any $\epsilon>0$, there exists
$v\in\mathbb{N},\bm{M}\in\mathbb{R}^{v\times(u+m)},\bm{N}\in\mathbb{R}^{v},\bm{C}\in\mathbb{R}^{m\times
v}$ such that

$\displaystyle\sup_{\bm{x}\in
X,\alpha\in\Delta^{m}}\left\|t(\bm{x},\bm{\alpha})-g(\bm{x},\bm{\alpha})\right\|\leq\epsilon,$

where
$g(\bm{x},\bm{\alpha})=\bm{C}\sigma(\bm{M}[\bm{x},\bm{\alpha}]^{\top}+\bm{N})$.

We define two matrices $\bm{R}\in\mathbb{R}^{u\times(2u+m)}$ and
$\bm{S}\in\mathbb{R}^{(2u+m)\times u}$ as follows:

$\displaystyle\bm{R}_{i,j}=\begin{cases}1,&\text{if }j=2i-1\\\ -1,&\text{if
}j=2i\\\ 0,&\text{otherwise}\end{cases},$

and

$\displaystyle\bm{S}_{i,j}=\begin{cases}1,&\text{if }i=2j-1\text{ or
}(i>2u\text{ and }j=u)\\\ -1,&\text{if }i=2j\\\
0,&\text{otherwise}\end{cases}.$

Define $m$ vectors $\bm{U}_{1},\ldots,\bm{U}_{m}\in\\{0,1\\}^{2u+m}$ as:

$\displaystyle(\bm{U}_{i})_{j}=\begin{cases}1,&j=2m+i\\\
0,&\text{otherwise}\end{cases}.$

Then, we have

$\displaystyle\bm{S}\sigma\left(\bm{R}\bm{x}+\sum_{i=1}^{m}\alpha_{i}\bm{U}_{i}\right)=[\bm{x},\bm{\alpha}].$

We can construct a MLP
$h(\bm{x};\bm{M},\bm{N},\bm{C},\bm{R},\bm{S},\bm{U})=\bm{C}\sigma(\bm{M}\bm{S}\sigma(\bm{R}\bm{x}+\bm{U})+\bm{N})$.

Let $\bm{\theta}_{0}=(\bm{M},\bm{N},\bm{C},\bm{R},\bm{S},\bm{0})$ and
$\bm{\theta}_{i}=(\bm{0},\bm{0},\bm{0},\bm{0},\bm{0},\bm{U}_{i}),i=1,\ldots,m$.
We have

$\displaystyle h(x;\bm{\theta}_{0}+\sum_{i=1}^{m}\alpha_{i}\bm{\theta}_{i})$
$\displaystyle=h(\bm{x};\bm{M},\bm{N},\bm{C},\bm{R},\bm{S},\sum_{i=1}^{m}\alpha_{i}\bm{U}_{i})$
$\displaystyle=\bm{C}\sigma(\bm{M}\bm{S}\sigma(\bm{R}\bm{x}+\sum_{i=1}^{m}\alpha_{i}\bm{U}_{i})+\bm{N})$
$\displaystyle=g(\bm{S}\sigma(\bm{R}\bm{x}+\sum_{i=1}^{m}\alpha_{i}\bm{U}_{i}))$
$\displaystyle=g(\bm{x},\bm{\alpha}).$

Since $\bm{\theta}_{i}$ consists of a single non-zero entry (equal to 1) with
all other elements being zero, it can be reshaped into a matrix
$\bm{B}_{i}\bm{A}_{i}$ with rank 1. ∎

##  Appendix B Proof of Proposition 3.2

######  Proposition B.1 ((Boyd & Vandenberghe, 2004)).

Given any $\bm{\alpha}\in\\{\bm{\alpha}~{}|~{}\alpha_{i}>0\\}$, the optimal
solution of the scalarized problem
$\min_{\bm{\theta}}\sum_{i=1}^{m}\alpha_{i}f_{i}(\bm{\theta})$ is a Pareto-
optimal solution of the original multi-objective optimization problem 1.

###### Proof.

Suppose $\bm{\theta}$ is the optimal solution of
$\sum_{i=1}^{m}\alpha_{i}f_{i}(\bm{\theta})$ but it is not Pareto optimal.
Based on the definition of Pareto optimal, there exists
$\bm{\theta}^{\prime}$, such that for $i\in[m]$, $f_{i}(\bm{\theta})\geq
f_{i}(\bm{\theta}^{\prime})$, and $\exists
i\in[m],f_{i}(\bm{\theta})>f_{i}(\bm{\theta}^{\prime})$. Since $\alpha_{i}>0$,
we have

$\sum_{i=1}^{m}\alpha_{i}(f_{i}(\bm{\theta})-f_{i}(\bm{\theta}^{\prime}))>0.$

It can be rewritten as:

$\sum_{i=1}^{m}\alpha_{i}f_{i}(\bm{\theta})>\sum_{i=1}^{m}\alpha_{i}f_{i}(\bm{\theta}^{\prime}),$

which contradicts the assumption that $\bm{\theta}$ is the optimal solution of
$\sum_{i=1}^{m}\alpha_{i}f_{i}(\bm{\theta})$. ∎

##  Appendix C Multi-Forward Regularization

Dimitriadis et al. (2023) propose the multi-forward regularization to penalize
the wrong ordering of solutions. Denote the set of current sampled reference
vectors as $\mathcal{V}\equiv\\{\bm{\alpha}^{1},\ldots,\bm{\alpha}^{b}\\}$.
Then, a directed graph $\mathcal{G}_{i}=(\mathcal{V},\mathcal{E}_{i})$ is
constructed for each task where
$\mathcal{E}_{i}=\\{(\bm{\alpha},\bm{\alpha}^{\prime})\in\mathcal{V}\times\mathcal{V}:\alpha_{i}<\alpha^{\prime}_{i}\\}$.
The multi-forward regularization loss is defined as:

$\displaystyle\mathcal{R}_{p}=\sum_{i=1}^{m}\log\left(\frac{1}{|\mathcal{E}_{i}|}\sum_{(\bm{\alpha},\bm{\alpha}^{\prime})\in\mathcal{E}_{i}}e^{[f(\bm{\theta}(\bm{\alpha}))-f(\bm{\theta}(\bm{\alpha}^{\prime}))]_{+}}\right).$

##  Appendix D Experimental Details

###  D.1 Hypervolume

Hypervolume (HV) (Zitzler & Thiele, 1998; Knowles et al., 2003) is a popular
indicator in multi-objective optimization (MOO), offering a measure of the
performance of the obtained solution set. Formally, for a given solution set
$\mathcal{P}$ and a reference point $\bm{r}$, the HV is defined as:

$\displaystyle
HV(\mathcal{P};\bm{r})=\Lambda(\\{\bm{q}\in\mathbb{R}^{m}~{}~{}|~{}~{}\exists\bm{p}\in\mathcal{P}:\bm{p}\geq\bm{q}\geq\bm{r}\\}),$
(10)

where $\Lambda$ denotes the Lebesgue measure. Figure 8 provides an
illustration of the HV indicator in a two-objective maximization problem. The
shaded area encapsulated by the solution set and the reference point
represents the HV.

Figure 8: Illustration of the hypervolume indicator.

For all datasets except UTKFace (Zhang et al., 2017), the reference point for
HV evaluation is set to $[0,0,\ldots,0]$, since $0$ is the smallest-possible
accuracy. For UTKFace, the first objective is the Huber loss (Huber, 1992),
not accuracy. Since $0.5$ is close to the observed largest Huber loss in the
experiment, we set the reference point to $[0.5,0,0]$.

###  D.2 Toy Problem

We use the two-objective toy problem adopted by (Liu et al., 2021a; Navon et
al., 2022; Dimitriadis et al., 2023), with parameters
$\bm{\theta}=[\theta^{1},\theta^{2}]\in\mathbb{R}^{2}$. The problem is
formulated as follows:

$\displaystyle\text{Minimize}~{}f_{1}(\bm{\theta})$
$\displaystyle=c_{1}(\theta)h_{1}(\theta)+c_{2}(\theta)g_{1}(\theta)~{}~{}\text{and}~{}~{}f_{2}(\bm{\theta})=c_{1}(\theta)h_{2}(\theta)+c_{2}(\theta)g_{2}(\theta),$
$\displaystyle~{}\text{where}~{}~{}h_{1}(\bm{\theta})$
$\displaystyle=\log{\big{(}\max(|0.5(-\theta^{1}-7)-\tanh{(-\theta^{2})}|,~{}~{}0.000005)\big{)}}+6,$
$\displaystyle h_{2}(\bm{\theta})$
$\displaystyle=\log{\big{(}\max(|0.5(-\theta^{1}+3)-\tanh{(-\theta^{2})}+2|,~{}~{}0.000005)\big{)}}+6,$
$\displaystyle g_{1}(\bm{\theta})$
$\displaystyle=\big{(}(-\theta^{1}+7)^{2}+0.1*(-\theta^{2}-8)^{2}\big{)}/10-20,$
$\displaystyle g_{2}(\bm{\theta})$
$\displaystyle=\big{(}(-\theta^{1}-7)^{2}+0.1*(-\theta^{2}-8)^{2})\big{/}10-20,$
$\displaystyle c_{1}(\bm{\theta})$
$\displaystyle=\max(\tanh{(0.5*\theta^{2})},~{}0)~{}~{}\text{and}~{}~{}c_{2}(\bm{\theta})=\max(\tanh{(-0.5*\theta^{2})},~{}0).$

###  D.3 MultiMNIST

Network Structure. Following (Dimitriadis et al., 2023), the base network
consists of a shared bottom and two task-specific heads. The shared bottom is
the LeNet (LeCun et al., 1998) with two convolution layers and a fully-
connected layer. Each task-specific head consists of two full-connect layers.
For PHN and PHN-HVI, we use the same hypernetwork structure as (Navon et al.,
2020b). The input preference vector $\bm{\alpha}$ first goes through a three-
layer MLP to get the ray embedding. Then, for each layer of the base network,
a linear layer is used to generate the base network parameters based on the
ray embedding.

Parameter Settings. Following (Dimitriadis et al., 2023), for LORPMAN and
PaMaL, we set the multi-forward regularization coefficient $\lambda_{p}$ to 0,
and window size $b$ to 4. The distribution parameters $p$ for sampling
$\bm{\alpha}$ is set to 1 for all algorithms. For PHN and PHN-HVI, we use the
same parameter setting as in the original paper. We use the Adam optimizer.
For COSMOS, the cosine similarity regularization coefficient $\lambda_{c}$ is
set to 1. The learning rate is set to $1e-3$ and the batch size is set to 256.

###  D.4 Census

Network Structure. Following (Dimitriadis et al., 2023), the base network
consists of a shared bottom and two task-specific heads. The shared bottom is
an one-layer MLP. Each task-specific head is a fully-connected layer. The
hypernetwork is constructed in the same way as for MultiMNIST.

Parameter Settings. Following (Dimitriadis et al., 2023), for LORPMAN and
PaMaL, we set the multi-forward regularization coefficient $\lambda_{p}$ to 5,
and window size $b$ to 2. The distribution parameters $p$ for sampling
$\bm{\alpha}$ is set to 1 for all algorithms. For PHN-HVI, we use the same
parameter setting as in the original paper. For COSMOS, the cosine similarity
regularization coefficient $\lambda_{c}$ is set to 1. We use the Adam
optimizer. The learning rate is set to $1e-3$ and the batch size is set to
256.

###  D.5 UTKFace

Network Structure. Following (Dimitriadis et al., 2023), the base network
consists of a shared bottom and three task-specific heads. The shared bottom
is a ResNet-18 (He et al., 2016). Each task-specific head is a fully-connected
layer.

Parameter Settings. Following (Dimitriadis et al., 2023), for LORPMAN and
PaMaL, we set the multi-forward regularization coefficient $\lambda_{p}$ to 1,
and window size $b$ to 3. The distribution parameters $p$ for sampling
$\bm{\alpha}$ is set to 2 for all algorithms. For COSMOS, the cosine
similarity regularization coefficient $\lambda_{c}$ is set to 1. We use the
Adam optimizer. The learning rate is set to $1e-3$ and the batch size is set
to 256.

###  D.6 CIFAR-100

CIFAR-100 has 20 5-way classification tasks:
1\. Aquatic Mammals: beaver, dolphin, otter, seal, whale
2\. Fish: aquarium fish, flatfish, ray, shark, trout
3\. Flowers: orchids, poppies, roses, sunflowers, tulips
4\. Food Containers: bottles, bowls, cans, cups, plates
5\. Fruits and Vegetables: apples, mushrooms, oranges, pears, sweet peppers
6\. Household Electrical Devices: clock, computer keyboard, lamp, telephone,
television
7\. Household Furniture: bed, chair, couch, table, wardrobe
8\. Insects: bee, beetle, butterfly, caterpillar, cockroach
9\. Large Carnivores: bear, leopard, lion, tiger, wolf
10\. Large Man-made Outdoor Things: bridge, castle, house, road, skyscraper
11\. Large Natural Outdoor Scenes: cloud, forest, mountain, plain, sea
12\. Large Omnivores and Herbivores: camel, cattle, chimpanzee, elephant,
kangaroo
13\. Medium-sized Mammals: fox, porcupine, possum, raccoon, skunk
14\. Non-insect Invertebrates: crab, lobster, snail, spider, worm
15\. People: baby, boy, girl, man, woman
16\. Reptiles: crocodile, dinosaur, lizard, snake, turtle
17\. Small Mammals: hamster, mouse, rabbit, shrew, squirrel
18\. Trees: maple, oak, palm, pine, willow
19\. Vehicles 1: bicycle, bus, motorcycle, pickup truck, train
20\. Vehicles 2: lawn-mower, rocket, streetcar, tank, tractor

Network Structure. Following (Liu et al., 2022), the base network consists of
a shared bottom and 20 task-specific heads. The shared bottom is a VGG-16
(Simonyan & Zisserman, 2014). Each task-specific head is a fully-connected
layer.

Parameter Settings. For LORPMAN and PaMaL, we set the multi-forward
regularization coefficient $\lambda_{p}$ to 1, and window size $b$ to 2. The
distribution parameters $p$ for sampling $\bm{\alpha}$ is set to 2 for all
algorithms. For COSMOS, the cosine similarity regularization coefficient
$\lambda_{c}$ is set to 1. Following (Liu et al., 2022), we use the SGD
optimizer. The learning rate is set to $1e-2$ and the batch size is set to 64.

###  D.7 CelebA

CelebA (Liu et al., 2015) has 40 binary classification tasks: 5 o’Clock
Shadow, Arched Eyebrows, Attractive, Bags Under Eyes, Bald, Bangs, Big Lips,
Big Nose, Black Hair, Blond Hair, Blurry, Brown Hair, Bushy Eyebrows, Chubby,
Double Chin, Eyeglasses, Goatee, Gray Hair, Heavy Makeup, High Cheekbones,
Male, Mouth Slightly Open, Mustache, Narrow Eyes, No Beard, Oval Face, Pale
Skin, Pointy Nose, Receding Hairline, Rosy Cheeks, Sideburns, Smiling,
Straight Hair, Wavy Hair, Wearing Earrings, Wearing Hat, Wearing Lipstick,
Wearing Necklace, Wearing Necktie, Young.

Network Structure. Following (Sener & Koltun, 2018), the base network consists
of a shared bottom and 40 task-specific heads. The shared bottom is a
ResNet-18 (He et al., 2016). Each task-specific head is a fully-connected
layer. Since CelebA has the overfitting problem (Kurin et al., 2022), we adopt
dropout regularization as in (Kurin et al., 2022) for all algorithms (i.e., we
add a dropout layer in each block as well as after the first convolution layer
and after average pooling layer).

Parameter Settings. For LORPMAN and PaMaL, we set the multi-forward
regularization coefficient $\lambda_{p}$ to 1, and window size $b$ to 3. The
distribution parameters $p$ for sampling $\bm{\alpha}$ is set to 2 for all
algorithms. For COSMOS, the cosine similarity regularization coefficient
$\lambda_{c}$ is set to 1. We use the Adam optimizer. The learning rate is set
to $1e-3$ and the batch size is set to 128.

###  D.8 Cityscapes

Network Structure. Following (Liu et al., 2021a; Navon et al., 2022;
Dimitriadis et al., 2023), the base network consists of a shared bottom and 2
task-specific heads. The shared bottom is a SegNet (Badrinarayanan et al.,
2017). Each task-specific head consists of two convolution layers.

Parameter Settings. Following (Dimitriadis et al., 2023), for LORPMAN and
PaMaL, we set the multi-forward regularization coefficient $\lambda_{p}$ to 1,
and window size $b$ to 3. The distribution parameters $p$ for sampling
$\bm{\alpha}$ is set to 7 for all algorithms. We use the Adam optimizer. The
initial learning rate is set to $1e-4$ and is halved after 75 epochs. The
batch size is set to 8.

##  Appendix E Pareto Front Obtained on CIFAR-100

Figure 9 shows the models obtained by COSMOS, PaMaL and LORPMAN. We can
observe that the solutions obtained by PaMaL have much lower accuracies while
the solutions obtained by COSMOS concentrate in a small region. The proposed
LORPMAN achieves good accuracy and diversity.

Figure 9: Test performance of COSMOS, PaMaL, and LORPMAN on CIFAR-100.


$V_{f}=\Gamma_{df}\cap(V\times B_{0}(\epsilon))\subset(V\times
B_{0}(\eta))\setminus Q\quad\text{whence}\quad\mu(V_{f})\leq\mu((V\times
B_{0}(\eta))\setminus Q)<\frac{1}{2}\,.$

Proposition 4.14 then implies that $\mu(T_{f}\setminus V_{f})\geq\frac{1}{2}$.
Since $T_{f}\setminus V_{f}=T\setminus V$, it follows that $\mu(T\setminus
V)\geq\frac{1}{2}$. Since $T_{g}\cap T\subset T\cap V$, we see that $T_{g}$
and $T\setminus V$ are closed disjoint sets. Moreover, it is easy to see that
both of them are solid. Finally, both of them have $\mu$-measure
$\geq\frac{1}{2}$, which is a contradiction to the assumption that
$\mu\in{\mathcal{P}}_{0}(M)$. The proof is complete. ∎

## References

  * [1] J. F. Aarnes.  Quasi-states and quasi-measures.  Adv. Math., 86(1):41–67, 1991.
  * [2] J. F. Aarnes.  Pure quasi-states and extremal quasi-measures.  Math. Ann., 295(4):575–588, 1993.
  * [3] J. F. Aarnes.  Construction of non-subadditive measures and discretization of Borel measures.  Fund. Math., 147(3):213–237, 1995.
  * [4] J. F. Aarnes and A. B. Rustad.  Probability and quasi-measures—a new interpretation.  Math. Scand., 85(2):278–284, 1999.
  * [5] S. Butler.  $q$-functions and extreme topological measures.  J. Math. Anal. Appl., 307(2):465–479, 2005.
  * [6] S. V. Butler.  Semisolid sets and topological measures.  Topology and its Applications, 310:108036, 2022.
  * [7] S. S. Cairns.  A simple triangulation method for smooth manifolds.  Bull. Amer. Math. Soc., 67:389–390, 1961.
  * [8] A. Dickstein and F. Zapolsky.  Approximation of quasi-states on manifolds.  J. Appl. Comput. Topol., 3(3):221–248, 2019.
  * [9] M. Entov and L. Polterovich.  Calabi quasimorphism and quantum homology.  Int. Math. Res. Not., (30):1635–1676, 2003.
  * [10] M. Entov and L. Polterovich.  Quasi-states and symplectic intersections.  Comment. Math. Helv., 81(1):75–99, 2006.
  * [11] M. Entov and L. Polterovich.  Rigid subsets of symplectic manifolds.  Compos. Math., 145(3):773–826, 2009.
  * [12] D. J. Grubb.  Irreducible partitions and the construction of quasi-measures.  Trans. Amer. Math. Soc., 353(5):2059–2072, 2001.
  * [13] F. F. Knudsen.  Topology and the construction of extreme quasi-measures.  Adv. Math., 120(2):302–321, 1996.
  * [14] C. Y. Mak, Y. Sun, and U. Varolgunes.  A characterization of heaviness in terms of relative symplectic cohomology.  Journal of Topology, 17(1):e12327, 2024.
  * [15] D. McDuff and D. Salamon.  Introduction to symplectic topology.  Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, third edition, 2017.
  * [16] L. Polterovich and D. Rosen.  Function theory on symplectic manifolds, volume 34 of CRM Monograph Series.  American Mathematical Society, Providence, RI, 2014.
  * [17] W. Rudin.  Real and complex analysis.  McGraw-Hill Book Co., New York, third edition, 1987.
  * [18] F. Schlenk.  Embedding problems in symplectic geometry, volume 40 of De Gruyter Expositions in Mathematics.  2005\.
  * [19] F. Schlenk.  Symplectic embedding problems, old and new.  Bull. Amer. Math. Soc. (N.S.), 55(2):139–182, 2018.
  * [20] E. M. Stein and R. Shakarchi.  Real analysis, volume 3 of Princeton Lectures in Analysis.  Princeton University Press, Princeton, NJ, 2005.  Measure theory, integration, and Hilbert spaces.

Adi Dickstein
---
Tel Aviv University
School of Mathematical Sciences
69978, Tel Aviv, Israel
E-mail<EMAIL_ADDRESS>

Frol Zapolsky
---
University of Haifa
Department of Mathematics
Faculty of Natural Sciences
3498838, Haifa, Israel
&
MI SANU
Kneza Mihaila 36
Belgrade 11001
Serbia
E-mail<EMAIL_ADDRESS>


# A Numerical System For Nested Spaces - Defining An Intuitive, Universal
Coordinate System For Self-Similarity

Petal Belle Mokryn

###### Abstract

In this paper I introduce a simple, universal numerical system for describing
all self-similar nested spaces. For a nested space made of $N>1$ smaller
copies of itself, the location of all points can be specified using the double
shift space $\\{0,1,...,N-1\\}^{\mathbb{Z}}$. Connectivity rules are
established to fully define the topology of the nested space, and immediate
consequences are investigated using the numerical system defined. I introduce
the numerical system and demonstrate how it unifies previous existing works
under a single, simple framework, to argue for its adoption as standard in
discussions of nested fractals.

##  1 Introduction

Ever since the 70’s, there has been a prevalent interest in self-similarity
and fractal spaces, with many famous examples such as the Cantor set and the
Sierpinski triangle, Julia sets, and more.
Mathematicians and physicists alike have been drawn to fractal mathematics
like moths to a flame, enticed by the plethora of new concepts hanging like
fruit ripe for the picking, that may be key to understanding many systems.
There are applications of fractal mathematics in Lattice Quantum Gravity [3],
condensed matter physics [18], stochastics [4], economics [22], and more.

One of the simplest kinds of fractals, and thus the most studied, are the
nested fractals. Roughly speaking, that means fractals made of some finite
$N>1$ number of smaller copies of themselves. Examples include the Cantor Set,
Sierpinski Gasket, Sierpinski Carpet, the Snowflake fractal, and more.

In this paper, I define a rigorous yet highly general notion of ”$N$-parts
nested spaces”, capturing much of the existing literature on the topic under a
single, general framework. I demonstrate that all nested spaces can be simply
and effectively described using the double shift space
$\\{0,1,...,N-1\\}^{\mathbb{Z}}$ equipped with a suitable topology. I define
an equivalence relation I call ”connectivity rules”, which defines a sort of
arithmetic on $\\{0,1,...,N-1\\}^{\mathbb{Z}}$, and fully details the
topological structure of nested spaces.

The numerical system introduced in this paper is a simple, effective way to
describe nested spaces, which generalizes all previous notations and
constructions, and gives an easy and effective form of notation, reminiscent
of positive real numbers.

##  2 Background Formulation

###  2.1 Defining Nested Spaces

Nesting, in this paper, is a topological property. First I will define which
sets can be nested sets/spaces. Using those definitions, I will then define
the $N$-parts nested cell-structure topology. Finally, nested spaces and
nested sets will be defined as sets that can be nested, endowed with either
the $N$-parts nested cell-structure topology or with the appropriate compact
subspace topology of it, respectively.

####  2.1.1 Definition 1: Nested Sets.

Let $S$ be a non-empty set. We say $S$ can be a $N$-parts nested set, if there
exist $N>1$ distinct, non-trivial, non-identity functions
$F_{0},...,F_{N-1}:S\to S$, such that each $F_{i}$ is defined on all of $S$,
and the following equation holds:

$S=\underset{i=0,...,N-1}{\bigcup}F_{i}\left[S\right]$ (1)

The set $S$, if endowed with and compact under the nested cell-structure
topology defined later in this paper, will then be called a $N$-parts nested
set, and the functions $F_{i}$ will be called its nesting relations. Note that
very few restrictions are placed on what kind of functions the nesting
relations actually are, as this paper aims to be as general as possible.
The following equation holds trivially:

$\forall
i=0,...,N-1:F_{i}\left[S\right]=F_{i}\left[\underset{j=0,...,N-1}{\bigcup}F_{j}S\right]=\underset{j=0,...,N-1}{\bigcup}\left(F_{i}\circ
F_{j}\right)\left[S\right]$ (2)

####  2.1.2 Definition 2: Nested Spaces.

We say a set $X$ can be a $N$-parts nested space if the following conditions
are satisfied:

  * •

$X$ is a countable nested union $X=\underset{n\in\mathcal{A}}{\bigcup}X_{n}$ ,
where $\mathcal{A}\subseteq\mathbb{N}$, and $k>0\in\mathcal{A}\Rightarrow
k-1\in\mathcal{A}$ .

  * •

Each $X_{n}$ can be a $N$-parts nested set, each with its own nesting
relations $\left\\{F_{n;i}\right\\}_{i=0}^{N-1}$

  * •

The following relation holds: $\forall
n,n+1\in\mathcal{A}:X_{n}=F_{n+1;0}\left[X_{n+1}\right]$

  * •

For all $n,n+1\in\mathcal{A},i\in\\{0,...,N-1\\}:$, the following diagram
commutes:

${X_{n+1}}$${F_{n+1;i}[X_{n+1}]}$${X_{n}}$${X_{n}}$$\scriptstyle{F_{n+1;0}}$$\scriptstyle{F_{n+1;i}}$$\scriptstyle{F_{n+1;0}}$$\scriptstyle{F_{n;i}}$
(3)

If $\left|\mathbb{A}\right|<\infty$, then a nested space is also a nested set.
It’s trivial to show that every nested set is a nested space, but not every
nested space is a nested set.

####  2.1.3 Defining Connectivity Rules

Plugging eq. 2 into eq. 1 and iterating, we get the following relation:

$S=\lim\limits_{M\to\infty}\underset{i_{0},...,i_{M-1}=0,...,N-1}{\bigcup}F_{i_{0}...i_{M-1}}\left[S\right]$
(4)

Where $F_{i_{0}...i_{M-1}}\left[S\right]=\left(F_{i_{0}}\circ...\circ
F_{i_{M-1}}\right)\left[S\right]$ are a generalization to all possible nesting
relations of the ”$M$-cells” indexed using ”words of length $M$”, introduced
in (Strichartz 2006)[21]. In this paper I call them ”base-$N$ words of length
$M$”, to be specific. By virtue of the nesting relations, and the fact that
set limits of the form $\lim\limits_{k\to\infty}A_{k},\forall k:A_{k+1}\subset
A_{k}$ always converge, there exist objects of the form

$F_{\omega}=\lim\limits_{M\to\infty}F_{i_{1}...i_{M}}\left[S\right]$ (5)

And they serve, as I will prove later, the topological role of ”points” under
the nested cell-structure topology.
Now that we have this concept of ”points”, we can thus define the
”connectivity rules” of $S$ as relations of the form

$F_{\omega_{1}}=F_{\omega_{2}}\,,\,\omega_{1}\neq\omega_{2}$ (6)

Where $F_{\omega_{1}},F_{\omega_{2}}$ are the topological points introduced in
eq. 5. We will be proving theorems about the connectivity rules and their
consequences later in this paper, after introducing a much more convenient
notation system to discuss nested spaces with.

####  2.1.4 The $N$-Parts Nested Cell-Structure Topology

Given a set $X$ that can be a nested space, we define its $N$-Parts Nested
Cell-Structure Topology $\tau_{\text{Nested}}$ as follows:

  * •

All $X_{n}$’s are members of $\tau_{\text{Nested}}$ : $\forall
n\in\mathcal{A}:X_{n}\in\tau_{\text{Nested}}$

  * •

For all $n\in\mathcal{A}$, and all $M\in\mathbb{N}/\\{0\\}$, all $M$-cells of
$X_{n}$ are members of $\tau_{\text{Nested}}$

  * •

All arbitrary unions of the sets mentioned above are members of
$\tau_{\text{Nested}}$

  * •

All finite intersections of the sets mentioned above are members of
$\tau_{\text{Nested}}$

If $|\mathcal{A}|<\infty$ , then $X$ is compact under $\tau_{\text{Nested}}$,
and we call $X$ both a $N$-parts nested space, and a $N$-parts nested set. If
$\mathcal{A}=\mathbb{N}$, then $X$ isn’t compact under $\tau_{\text{Nested}}$,
and we only call $X$ a $N$-parts nested space. All nested sets are nested
spaces, but not all nested spaces are nested sets.
Note that all objects $F_{n;\omega}$, with $\omega$ a base-$N$ word of length
$\infty$, are topologically points under $\tau_{\text{Nested}}$ because they
have Lebesgue covering dimension zero.

###  2.2 Defining The Numerical System $[T_{N}]_{X}$

####  2.2.1 Defining the $N$-Parts Numbers $T_{N}$

Let us define the double shift space
$\left\\{0,1,...,N-1\right\\}^{\mathbb{Z}}$, and for all
$p\in\left\\{0,1,...,N-1\right\\}^{\mathbb{Z}}$ we use notation
$p=...p_{1}p_{0}.p_{-1}p_{-2}...$ , as if we’re writing a base-$N$ positive
real number. Let us also restrict to
$T\subset\left\\{0,1,...,N-1\right\\}^{\mathbb{Z}}$, such that for all $p\in
T$, there must exist some $n\in\mathbb{N}$ such that $\forall j>n:p_{j}=0$,
meaning that if we were to endow $T$ with the real number line topology, all
$p\in T$ would be finite.

We define the $N$-parts nested cell-structure topology $\tau_{N}$ on $T$ as
follows:

  * •

For all $k\in\mathbb{Z}$, and all base-$N$ natural numbers $A$, the base-$N$
real number interval
$I=N^{k}\cdot\left[A.\overline{0},A.\overline{N-1}\right)$ is a member of
$\tau_{N}$

  * •

All arbitrary unions of such intervals are members of $\tau_{N}$

  * •

All finite intersections of such intervals are members of $\tau_{N}$

The restricted double shift space $T$ endowed with the $N$-parts nested cell-
structure topology $\tau_{N}$ is now called the $N$-parts numbers, and marked
$T_{N}$.

####  2.2.2 Charting $N$-Parts Nested Spaces with $(n,\omega)$

Let us consider a $N$-parts nested space $X$ with $\mathcal{A}=\mathbb{N}$,
and the series of $N$-parts nested sets it’s made of
$\left\\{X_{n}\right\\}_{n=0}^{\infty}$ .

Let us define a set $\mathbb{K}_{N}$ of all ordered pairs $(n,\omega)$,
where $n\in\mathbb{N}$ and $\omega$ is a base-$N$ word of length $\infty$.
For all base-$N$ words $\omega=\omega_{0}...\omega_{M-1}$ of finite length
$M<\infty$ , we can amend $\omega$ to be a base-$N$ word of length $\infty$ by
changing it to $\omega=\omega_{0}...\omega_{M-1}0000....$
The ordered pairs $(n,\omega)\in\mathbb{K}_{N}$ now map all points in $X$
using the surjective mapping

$\tilde{F}_{X}(n,\omega)=F_{n;\omega}[X_{n}]$ (7)

####  2.2.3 Charting $N$-Parts Nested Spaces using $T_{N}$

We can now define another surjective mapping, $G(n,\omega):\mathbb{K}_{N}\to
T_{N}$, defined as follows:
Given $(n,\omega)\in\mathbb{K}_{N}$, we write out explicitly
$\omega=\omega_{0}\omega_{1}...$. Let us define $G(n,\omega)=p$, such that
$p=...p_{1}p_{0}.p_{-1}p_{-2}...\in T_{N}$, and for each specific digit
$\omega_{k},k\in\mathbb{N}$ of $\omega$, the digits of $p$ are assigned as
follows:

  * •

$\forall k\in\mathbb{N}:p_{n-k}=\omega_{k}$

  * •

$\forall j>n:p_{j}=0$

The mapping $G$ is not invertible, because there are different
$\mathbb{K}_{N}$, $(n_{1},\omega_{1})\neq(n_{2},\omega_{2})$ that get mapped
to the same $p\in T_{N}$. A limited inverse
$\tilde{G}^{-1}:T_{N}\to\mathbb{K}_{N}$ can still be defined:
Given any $p\in T_{N}$, let $n$ be the largest natural number such that the
digit $p_{n}$ of $p$ is non-zero. If such a number doesn’t exist, then let
$n=0$. We now define $\tilde{G}^{-1}(p)=(n,\omega)$ where the digits of
$\omega$ are assigned $\forall k\in\mathbb{N}:\omega_{k}=p_{n-k}$

The ”inverse” $\tilde{G}^{-1}$ now allows us to define a surjective mapping

$M_{X}=\left(\tilde{F}_{X}\circ\tilde{G}^{-1}\right):T_{N}\to X$ (8)

From $T_{N}$ to any $N$-parts nested space $X$, allowing us to chart $X$ with
coordinates $T_{N}$.

####  2.2.4 The Quotient Space $[T_{N}]_{X}$ Homeomorphic to $X$

The coordinate chart $M_{X}:T_{N}\to X$ , on its own, doesn’t give us a
complete topological description of $X$. To do that, we also need to describe
the connectivity rules of $X$ in $T_{N}$.
Let us define on $T_{N}$ an equivalence relation $\stackrel{{\scriptstyle
X}}{{\sim}}$ , such that

$\forall a,b\in T_{N}:a\stackrel{{\scriptstyle x}}{{\sim}}b\Leftrightarrow
M_{X}(a)=M_{X}(b)$ (9)

For any $N$-parts nested space $X$, we call the equivalence relation
$\stackrel{{\scriptstyle x}}{{\sim}}$ defined on $T_{N}$ by $X$ the
Connectivity Rules of $X$.

Let us now define the quotient space
$[T_{N}]_{X}\triangleq\nicefrac{{T_{N}}}{{\stackrel{{\scriptstyle
x}}{{\sim}}}}$ , equipped with the quotient space topology
$\nicefrac{{\tau_{N}}}{{\stackrel{{\scriptstyle x}}{{\sim}}}}$ .
Restricting $M_{X}$ to $[T_{N}]_{X}$, the mapping $M_{X}:[T_{N}]_{X}\to X$ is
a bijection, and note that the nested cell-structure topology
$\tau_{\text{Nested}}$ is exactly the final topology of
$\nicefrac{{\tau_{N}}}{{\stackrel{{\scriptstyle x}}{{\sim}}}}$ induced on $X$
by $M_{X}$, making $M_{X}$ a homeomorphism.

In conclusion, for all $N$-parts nested spaces with $\mathcal{A}=\mathbb{N}$:

$X\cong[T_{N}]_{X}$ (10)

Under homeomorphism $M_{X}:[T_{N}]_{X}\to X$

To chart a nested set with $|\mathcal{A}|=K<\infty$,
Simply restrict $T_{N}$ to the shift space
$\\{0,1,...,N-1\\}^{\\{K,K-1,...\\}}\subset T_{N}$ before taking the quotient
by $\stackrel{{\scriptstyle x}}{{\sim}}$

###  2.3 Arithmetic Operations on $T_{N}$ and Their Implications on
$[T_{N}]_{X}$

Lastly, we need to consider arithmetic operations on $T_{N}$ , and their
implications on $[T_{N}]_{X}$. The usual arithmetic operations on base-$N$
positive real numbers can be used, but they may not have the same
interpretation for general nested spaces as they have for the positive real
numbers in ordinary use. In fact, they can be completely nonsensical for some
nested spaces.
There are two operations that do have a simple, intuitive interpretation for
all nested spaces.

####  2.3.1 Scaling

The first operation we define is multiplication by integer powers of $N$,
which we will call according to its intuitive interpretation, scaling, or
shift.

$\text{Sc}:T_{N}\times\mathbb{Z}\to T_{N}:\;\text{Sc}(a,k)=N^{k}\cdot a$ (11)

We’ll simply mark the scaling operation using ”$N^{k}\cdot$” or ”$\cdot
N^{k}$” in future use, for simplicity. Note that the scaling operation $\cdot
N^{k}$ for all $k\in\mathbb{Z}$ preserves connectivity rules, meaning
$a\stackrel{{\scriptstyle x}}{{\sim}}b\Leftrightarrow N^{k}\cdot
a\stackrel{{\scriptstyle x}}{{\sim}}N^{k}\cdot b$, and that the scaling
operation also defines an equivalence relation on $[T_{N}]_{X}$.

####  2.3.2 Imposition

Another operation with clear intuitive interpretation, is one we’ll have to
define algorithmically. I call this operation imposition. $a\leftslice b$, or
$a$ impose $b$, and it’s a set-valued operation defined by the following
pseudocode:

function $\leftslice$($a,b$)

define $tempA$ := $a$

define $tempB$ := $b$

define $ConnectedA$ := $\left\\{p\in T_{N}\Big{|}a\stackrel{{\scriptstyle
x}}{{\sim}}p\right\\}$

define $ConnectedB$ := $\left\\{p\in T_{N}\Big{|}b\stackrel{{\scriptstyle
x}}{{\sim}}p\right\\}$

define $Imposed=\\{\\}$

for all $A\in ConnectedA$ do

for all $B\in ConnectedB$ do

define $temp$ := $A$

for all $i\in\mathbb{Z}$ do

if $A$.digits[$i$] == 0 then

$temp$.digits[$i$] := B.digits[$i$]

end if

end for

$Imposed$.AddMember[$temp$]

end for

end for

return $Imposed$

end function

The intuitive meaning of $a\leftslice b$ is ”start at $a$, and ’walk in the
direction’ of $b$ in all ways the connectivity rules of the nested space $X$
allow”.
Note that the operation of imposition also preserves connectivity rules,
meaning that $\forall a,b,c\in T_{N}:a\stackrel{{\scriptstyle
x}}{{\sim}}b\Rightarrow(a\leftslice c)=(b\leftslice c)$
In actual usage, we likely won’t be working with the entire set $a\leftslice
b$, but rather only with specific useful members of it.

##  3 Consequences

###  3.1 Properties of Nested Spaces and Connectivity Rules

  1. 1.

Given a connectivity rule $a\stackrel{{\scriptstyle x}}{{\sim}}b$ , where
$a,b\in T_{N}$, it’s easy to prove $\forall k\in\mathbb{Z}:(N^{k}\cdot
a)\stackrel{{\scriptstyle x}}{{\sim}}(N^{k}\cdot b)$ as they are essentially
the same connectivity rule, either in different $X_{n}$’s or in different
M-cells of $X_{0}$.
Such connectivity rules are to be recognized as equivalent to each other, so
we define the set of connectivity rules of a $N$-parts nested space modulo
this equivalence. We define the set of connectivity rules of a nested space
$X$ as the quotient set:

$C_{X}=\nicefrac{{\left(\nicefrac{{\left\\{\\{a,b\\}|a,b\in
T_{N},a\stackrel{{\scriptstyle x}}{{\sim}}b\right\\}}}{{\left\\{\\{p,p\\}|p\in
T_{N}\right\\}}}\right)}}{{\cdot N^{k}}}$ (12)

And we call its cardinality $|C_{X}|$ the number of connectivity rules in $X$.
Note that if $|C_{X}|<\infty$, then $X$ is post-critically finite.

  2. 2.

Given a $N$-parts nested space $X$, a set of connected points in $X$ is any
set $S$ of unordered pairs $\\{a,b\\}$, such that $a,b\in T_{N}$ and
$a\stackrel{{\scriptstyle x}}{{\sim}}b$ .

We call a Basis of Connectivity Rules of $X$, any set $G$ of connected points
in $X$ such that all of $C_{X}$ can be defined from $G$ using the operations
of scaling and imposition.

Finally, we call a Generator of Connectivity Rules $G_{X}$ of $X$, any basis
of connectivity rules $G_{X}$ of $X$, such that for all other basis
$G^{\prime}$ of connectivity rules of $X$, $|G_{X}|\leq|G^{\prime}|$ .

  3. 3.

Hypothesis:
For all $N>1$, there exists some finite $K(N)\in\mathbb{N}$ , such that for
all $N$-parts nested spaces $X$ :

$|G_{X}|\leq K(N)$ (13)

Should this hypothesis prove to be true, I will call a $N$-parts nested space
$X$ with $|G_{X}|=K(N)$ Maximally Connected.

  4. 4.

Given a $N$-parts nested space $X$ with $\mathcal{A}=\mathbb{Z}$, for all
$i\in\\{0,1,...,N-1\\},k\in\mathbb{Z}$, we call the interval
$I_{i,k}=N^{k}\cdot\left[i.\overline{0},i.\overline{N-1}\right)$ the $i$-th
part of $X$ at scale $k$.

We call $I_{i,k}$ an edge part of $X$ if the connectivity rule
$0.\overline{i}\stackrel{{\scriptstyle x}}{{\sim}}i.\overline{0}$ holds.

If no such connectivity rule holds, but other types of connectivity rules do
exist for $I_{i,k}$, then I call $I_{i,k}$ a middling part of $X$ at scale
$k$.

  5. 5.

Hypothesis:
If a $N$-parts nested space $X$ is path-connected, then every middling part
$I_{a,k}$ of $X$ at scale $k$ has at least two connectivity rules, such that
$I_{a,k}$ is connected to at least two other parts of $X$ at scale $k$.

  6. 6.

Ease of usage:
$T_{N}$ charts cells of any size, anywhere in the $N$-parts nested space,
using real number intervals of the form
$I=N^{k}\cdot\left[A.\overline{0},A.\overline{N-1}\right)$

  7. 7.

Ease of usage:
For a nested space $X$, existing literature often defines vertex sets
$V_{...}$ as the boundaries of a corresponding $M$-cell $F_{...}$ of a
specific $X_{n}$ . In $[T_{N}]_{X}$, that simply means taking the boundary
under topology $\nicefrac{{\tau_{N}}}{{\stackrel{{\scriptstyle x}}{{\sim}}}}$
of the real number intervals
$I=N^{k}\cdot\left[A.\overline{0},A.\overline{N-1}\right)$

###  3.2 Example Nested Space: The Positive Real Number Line

The positive real number line can be defined in a way similar to how
(Strichartz 2006)[21] defined the unit interval, but more straightforward:
We define the positive real number line as a 2-parts nested space charted by
$T_{2}$, with the connectivity rule $0.\overline{1}\sim 1.\overline{0}$. The
arithmetic operation of addition then trivially follows from this connectivity
rule used together with scaling and imposition.

In fact, the positive real number line and its arithmetic can also be defined
as a $N$-parts nested space of any natural $N>1$, using $T_{N}$ together with
the connectivity rule $\forall
i=0,...,N-2:i.\overline{(N-1)}\sim(i+1).\overline{0}$.

As a matter of fact, for $N=10$ we get
an incredibly familiar-looking connectivity rule, $0.\overline{9}\sim 1$ !

Furthermore, by restricting the number of digits either to the left or to the
right of the decimal dot on $[T_{N}]_{\mathbb{R}_{+}}$, one can easily define
either finite intervals on $\mathbb{R}_{+}$ or the natural numbers,
respectively.

###  3.3 Example Nested Space: The Extended Sierpinski Triangle

The infinitely extended Sierpinski triangle with infinite detail, like those
shown by Fukushima [10] and Shima [20], can be defined as a 3-parts nested
space charted by $T_{3}$ with the connectivity rules $\forall
i,j=0,1,2:i.\overline{j}\sim j.\overline{i}$

There are two other popular constructions in literature of the Sierpinski
triangle:

  1. 1.

A construction like that done by Strichartz [21], analogous to the unit
interval on $\mathbb{R}_{+}$ ; a 3-parts nested set Sierpinski triangle,
compact in $\mathbb{R}^{2}$ and containing infinite detail.

  2. 2.

A construction like that done by Rammal [19], made by joining together
triangles of defined elementary size to form a finitely detailed but
infinitely extended Sierpinski triangle in $\mathbb{R}^{2}$, analogous to the
natural numbers.

Both of these constructions are easily achieved from our definition of the
3-parts nested space Sierpinski triangle above, simply by restricting the
number of digits to the left or to the right of the decimal point,
respectively, in exactly the same way we defined the finite interval and
natural numbers in Sec. 3.2.

##  4 What’s Next?

There is much work left to be done on this project of mine.

###  4.1 Scope: Undergrad Project

First, should I find an advisor this semester, I would like to start by
engaging with my hypothesis, and by simply translating the existing body of
work on the dynamics of nested fractals to my $T_{N}$ notation.
That means, doing either part or all of the following list:

  * •

Trying to prove my hypothesis shown above, and any other useful insights.

  * •

Translating and generalizing the laplacian on nested fractals defined by the
likes of Kigami [16], Strichartz [21], Shima [20] and more to my coordinate
system $T_{N}$

  * •

Translating the method of spectral decimation, shown by the likes of Rammal
[19], Strichartz [21] and more as the go-to method in existing literature to
solving differential equations on fractals, to my coordinate system $T_{N}$

  * •

Translating the eigenfunctions of the laplacian on nested fractals, the
harmonic functions in particular, to their expressions as functions of
$[T_{N}]_{X}$

  * •

Translating and generalizing the fractal Green’s functions shown by Kigami
[17] to their expressions as functions of $T_{N}$

  * •

Engaging with work on the properties of dynamics on fractals, such as that
done by Akkermans [2].

  * •

Translating the gradient and harmonic/”finite energy” coordinates shown by the
likes of Tepylaev [23], Kelleher [15] and Hinz [11].

  * •

Comparing and contrasting the cases of analysis on finitely and infinitely
ramified (see Barlow [5]) fractals using the language of $T_{N}$, looking for
any useful insights that may arise.

###  4.2 Scope: Advanced Degree

In further future work, potentially as a Masters/PhD project, I would also
like to try the following:

  * •

Engage with and try to generalize the work on differential forms on fractals,
done by Kelleher [15], Aaron [1], Cipriani [8], and Hinz [12] from the
perspective of $T_{N}$ notation.

  * •

Use $T_{N}$ construction and notation to try and generalize the field of
algebraic topology as a whole, cohomology in particular, to work on nested
spaces.
I wish to do so by defining an equivalent to simplexes and chain-complexes,
either on $T_{N}$, or on some specific $[T_{N}]_{X}$’s with unique properties,
possibly the maximally connected $N$-parts nested spaces, if they do indeed
exist.

  * •

Try and engage with further work on the topic from the perspective of $T_{N}$
coordinates, such as that done by Hu [13], David [9], Ionescu [14], Berthé
[7], Bedford [6], and more.

## Acknowledgements:

I would like to thank Prof. Eric Akkermans for introducing me to the topic of
analysis on nested fractals. You’ve enriched me and helped me study this
topic, as well as mathematics in general, to a level beyond what I could’ve
otherwise learned in undergrad.

## References

  * [1] Skye Aaron, Zach Conn, Robert Strichartz and Hui Yu  “Hodge-de Rham theory on fractal graphs and fractals”  In _arXiv preprint arXiv:1206.1310_ , 2012
  * [2] Eric Akkermans et al.  “Spatial log-periodic oscillations of first-passage observables in fractals”  In _Physical Review E_ 86.6 APS, 2012, pp. 061125
  * [3] J Ambjorn, Jerzy Jurkiewicz and Renate Loll  “Lattice quantum gravity-an update”  In _arXiv preprint arXiv:1105.5582_ , 2011
  * [4] Christoph Bandt, Siegfried Graf and Martina Zähle  “Fractal geometry and stochastics”  Springer, 1995
  * [5] Martin T Barlow and Richard F Bass  “Brownian motion and harmonic analysis on Sierpinski carpets”  In _Canadian Journal of Mathematics_ 51.4 Cambridge University Press, 1999, pp. 673–744
  * [6] Tim Bedford  “Dimension and dynamics for fractal recurrent sets”  In _Journal of the London Mathematical Society_ 2.1 Oxford University Press, 1986, pp. 89–100
  * [7] Valérie Berthé et al.  “Fractal tiles associated with shift radix systems”  In _Advances in mathematics_ 226.1 Elsevier, 2011, pp. 139–175
  * [8] Fabio Cipriani, Daniele Guido, Tommaso Isola and Jean-Luc Sauvageot  “Differential 1-forms, their integrals and potential theory on the Sierpinski gasket”  In _arXiv preprint arXiv:1105.1995_ , 2011
  * [9] Claire David  “A note on energy forms on fractal domains”  In _arXiv preprint arXiv:1704.04518_ , 2017
  * [10] Masatoshi Fukushima and Tadashi Shima  “On a spectral analysis for the Sierpinski gasket”  In _Potential Analysis_ 1 Springer, 1992, pp. 1–35
  * [11] Michael Hinz and Alexander Teplyaev  “Finite energy coordinates and vector analysis on fractals”  In _Fractal geometry and stochastics V_ , 2015, pp. 209–227  Springer
  * [12] Michael Hinz and Alexander Teplyaev  “Vector analysis on fractals and applications”, 2012  arXiv:1207.6375 [math.AP]
  * [13] Jiaxin Hu  “Nonlinear partial differential equations on fractals”  University of St. Andrews (United Kingdom), 2001
  * [14] Marius Ionescu, Luke G Rogers and Alexander Teplyaev  “Derivations and Dirichlet forms on fractals”  In _Journal of Functional Analysis_ 263.8 Elsevier, 2012, pp. 2141–2169
  * [15] Daniel J Kelleher  “Differential forms for fractal subspaces and finite energy coordinates”  In _arXiv preprint arXiv:1701.02684_ , 2017
  * [16] Jun Kigami  “Analysis on fractals”  Cambridge University Press, 2001
  * [17] Jun Kigami, Daniel R Sheldon and Robert S Strichartz  “Green’s functions on fractals”  In _Fractals_ 8.04 World Scientific, 2000, pp. 385–402
  * [18] S.H. Liu  “Fractals and Their Applications in Condensed Matter Physics” 39, Solid State Physics  Academic Press, 1986, pp. 207–273  DOI: https://doi.org/10.1016/S0081-1947(08)60370-7
  * [19] Rammal Rammal and Gérard Toulouse  “Spectrum of the Schrödinger equation on a self-similar structure”  In _Physical review letters_ 49.16 APS, 1982, pp. 1194
  * [20] Tadashi Shima  “Lifschitz tails for random Schrödinger operators on nested fractals”, 1992
  * [21] Robert S Strichartz  “Differential equations on fractals: a tutorial”  Princeton University Press, 2006
  * [22] Hideki Takayasu et al.  “Fractal properties in economics”  In _arXiv preprint cond-mat/0008057_ , 2000
  * [23] Alexander Teplyaev  “Harmonic coordinates on fractals with finitely ramified cell structure”  In _Canadian Journal of Mathematics_ 60.2 Cambridge University Press, 2008, pp. 457–480