Multi-Task Learning as Multi-Objective Optimization

研究的背景

多任务学习可以看做是一个多目标优化问题，因为不同的任务可能会互相冲突，需要进行权衡。一个折中的办法是优化一个代理目标函数，让它可以最小化每个任务的loss的线性加权组合；然而这种方法只有在它们不竞争的时候才可以使用。
以往有许多相关工作是基于梯度的多目标优化，但是他们并不适合直接用于大规模的学习问题，因为它们随着梯度维度的上升和数量的增加变得难以扩展。
Stein认为，如果要估计高斯随机变量，最好是从所有样本中估计三个或三个以上变量的均值，而不是分别单独进行估计，即使这些高斯变量是相互独立的。这就是Stein悖论，也是探索多任务学习的早期动机。但是MTL 的潜在优势超出了 Stein 悖论的直接含义，因为即便是真实世界中看似无关的任务也因数据共享的过程而存在很强的依赖性。

使用的方法（创新点）

明确地将多任务学习转换成多目标优化，总目标是找到帕累托最优解。鉴于背景2，作者提出了多目标损失的上界，并证明了它可以被有效地优化，然后进一步证明了优化这个上界会产生帕累托最优解。
基础知识：
- 如果一个解的损失函数小于等于另一个解的损失函数，那么我们说这个解支配另一个解。
- 如果没有其他解能够支配这个解，那么这个解就是帕累托最优解。
- 由密集的帕累托最优解构成的曲线就是帕累托前沿。
- 作者使用向量值loss定义了MTL的多目标优化公式：
  $$
  \min_{\substack{\pmb{\theta}^{sh},\\ \pmb{\theta}^1,\cdots,\pmb{\theta}^T} }\pmb{L}(\pmb{\theta}^{sh},\pmb{\theta}^1,\cdots,\pmb{\theta}^T)=\min_{\substack{\pmb{\theta}^{sh},\\ \pmb{\theta}^1,\cdots,\pmb{\theta}^T} }(\pmb{\hat{\mathcal{L} } }^1(\pmb{\theta}^{sh},\pmb{\theta}^1),\cdots,\pmb{\hat{\mathcal{L} } }^T(\pmb{\theta}^{sh},\pmb{\theta}^T))^T
  $$
  其中，$\theta^{sh}$和$\theta^t$分别指的是在多个任务之间共享的参数和每个任务所特有的参数。
多梯度下降算法(MGDA，2012)
- 关于KKT最优化条件：KKT条件的引入推广了拉格朗日乘数法，拉格朗日乘数法原本只是解决等式约束下的优化问题，而引入KKT条件的拉格朗日乘数法可用于更普遍的有不等式约束的情况。
- 如何将等式约束+不等式约束转换为无约束的简单优化问题：先把不等式约束条件转化为等式约束条件——引入松弛变量(比如在小于等于的约束条件左侧加上一个平方项，将不等式变成等式)，即KKT乘子。再把等式约束转化为无约束优化问题——引入拉格朗日乘子。
- 关于不等式约束优化问题：
  
  假设我们希望最小化$f(x)$，不等式约束条件为$g(x)\le0$，然后引入松弛变量将不等式转化为等式约束$g(x)+a^2=0$。
  
  约束不等式$g(x)\le0$ 称为**原始可行性(primal feasibility)**，据此我们定义可行域(feasible region) $K={x∈R^n|g(x)\le 0}$。由Lagrange乘数法中对松弛变量a的求导有$2a\lambda=0$，分开两种情况讨论：
  
  (1) $\lambda=0,a\ne 0$，这时约束条件是无效的(inactive)，那么$g(x)<0$，最佳解位于 $K$ 的内部，称为内部解(interior solution)；
  
  (2) $\lambda\ge0,a=0$，$\lambda$必定不会小于0，此结论后续会说明，此时约束条件是有效的(active)，$g(x)=0$ ，最佳解落在 $K$ 的边界，称为边界解(boundary solution)。
  
  因为我们希望最小化 f ，梯度 $\nabla f$ (函数 f 在点 x 的最陡上升方向)应该指向可行域 K 的内部(因为你的最优解最小值是在边界取得的)，但 $\nabla g$ 指向 K 的外部(即 g(x)>0 的区域(因为你的约束是小于等于0)，因此为了满足拉格朗日数乘法必有$\lambda \ge0$ **，称为对偶可行性(dual feasibility)**。
  
  合并两种情形，当有：$\lambda g(x)=0$，且在约束起作用时$\lambda>0，g(x)=0$，约束不起作用时$\lambda=0，g(x)<0$。不论是内部解或边界解， λg(x)=0 恒成立，这称之为**互补松弛性(complementary slackness)**。整合上述两种情况，最佳解的必要条件包括拉格朗日函数 $L(x,λ)$ 的定常方程式、原始可行性、对偶可行性，以及互补松弛性：
  $$
  \nabla_xL=\nabla f+\lambda\nabla g=0\\g(x)\le 0\\ \lambda\ge 0\\ \lambda g(x)=0.
  $$
  
  这些条件合称为Karush-Kuhn-Tucker (KKT)条件。如果我们要最大化 $f(x)$ 且受限于 $g(x)\le 0$ ，那么对偶可行性要改成 $λ\le 0$ 。
- 对于这个优化问题，如果结果为0则得出满足KKT条件的点；如果不为0则该解决方案给出了改善所有任务的下降方向。因此，最终的MTL算法将是针对特定任务参数的梯度下降，然后求解上图公式，并应用$\sum_{t=1}^T\alpha^t\nabla_{\theta^{sh}}$作为共享参数的梯度更新策略。
解决优化问题
- 对于两个任务的情况，$\alpha、1-\alpha$分别为两个loss的权重，可以直接计算出解析解。而对于更普遍的多任务情况，可以使用Frank-Wolfe算法求解它。
- Frank-Wolfe算法：
- 基于上述FW算法实际上已经可以解决MTL问题，但是并不高效：因为对于每个任务都需要将共享参数进行一次反向传播，这样的冗余重复了多次，降低了算法的运行速度，因此作者再次针对编码器解码器结构提出了更高效的优化，使得其优化了目标的上界，并且只需要反向传播参数一次。由链式法则显然有公式(6)中的上界，其中右式的第一个范数是z关于共享参数的雅克比矩阵。
  
  这个上界有两个很好的属性：首先，对每个任务而言，loss关于z的导数可以在一次反向传播被计算完成；其次，雅克比范数矩阵不是待求权重的函数，因此目标函数中可以将其无视掉，进一步减小计算量。最终，我们的优化问题就变成了下图中的公式。
- 最后，作者证明了一个引理，说明了尽管MGDA-UB是原始优化问题的近似值，但是依旧产生了帕累托最优解。引理和证明过程不做关注。