梯度下降算法（Gradient Descent Algorithm）
梯度下降算法是机器学习领域最常见的目标优化算法之一：目标损失函数$\ell(\theta)$关于参数$\theta$的梯度是损失函数上升最快的方向，而我们的目标是最小化损失函数$\ell(\theta)$，因此需要将参数沿着梯度相反的方向前进一个步长$\eta$，就可以实现损失函数的下降，其中$\eta$又称为学习率。梯度下降算法的更新过程如下
$\theta \leftarrow \theta-\eta\cdot\nabla\ell(\theta)$
对于无约束的单目标优化问题$\min f(x)$，能够利用梯度下降算法进行优化：$x_{k+1}=x_k+\alpha_kd_k$，其中$\alpha_k$为步长，$d_k$为更新方向。当$d_k=-\nabla f(x_k)$时，即为标准的梯度下降算法，也叫最速下降算法。证明如下：
首先对$f(x_{k+1})$进行泰勒展开
$f(x_{k+1})=f(x_k+\alpha_kd_k)=f(x_k)+\alpha_k\nabla f(x_k)^Td_k+O(\alpha_k),\;\alpha_k>0$
则目标函数沿着$d_k$方向更新的速率为
$\lim_{\alpha_k\to0}\frac{f(x_k+\alpha_kd_k)-f(x_k)}{\alpha_k}=\lim_{\alpha_k\to0}\frac{\alpha_k\nabla f(x_k)^Td_k+O(\alpha_k)}{\alpha_k}=\nabla f(x_k)^Td_k=||\nabla f(x_k)||\cdot||d_k||cos\theta$
其中$\theta$为梯度$\nabla f(x_k)$与更新方向$d_k$之间的夹角，若要使函数$f(x_k)$沿着$d_k$下降（即$f(x_k+\alpha_kd_k)<f(x_k)$），则有$\theta>90\degree$；要使得下降速率最大，则夹角$\theta=180\degree$，即更新方向$d_k$为梯度的反方向$-\nabla f(x_k)$。此时$d_k$可以表示成如下优化
$d_k=\arg\min_d\;\{\nabla f(x_k)^Td+\frac 12||d||^2\}$
上述优化目标同时对$d$的方向和大小进行优化，保证更新方向$d$能够有效减少目标函数值的同时，控制$d$的大小。其中$\frac 12||d||^2$为正则项，确保更新方向$d$不会过大，从而避免更新步长过大导致的不稳定性。
该优化问题的解可以令导数为零来求解，即
$\nabla f(x_k)+d=0\Longrightarrow d=-\nabla f(x_k)$
多重梯度下降问题描述
上面可以看出，梯度下降的本质其实是找到一个搜索方向$d_k$，使得目标函数沿着$d_k$的更新速率为负$f(x_k)^Td_k<0$。那么对于$m$多目标问题，如果能找到一个搜索方向$d_k$，使得$f_i(x_k)^Td_k<0,\;\forall i\in m$，则该方向会使得所有目标函数都沿下降的方向更新。
类似单目标梯度下降，多目标梯度下降方向的求解，可以表示为下面一个最小-最大优化问题
$d_k=\arg\min_d\;\{\max_i\nabla f_i(x_k)^Td+\frac{1}{2}||d||^2\}\qquad (1)$
这个问题的目标是找到一个搜索方向$d_k$，使得在所有目标函数的更新速率$\nabla f_i(x_k)^Td$中，连最大的那个更新速率值都尽可能小。
但式$(1)$并不好直接求解，我们可以将其改写为如下形式的约束优化问题
$\begin{cases}(d_k,\alpha_k)=\min\{\alpha+\frac{1}{2}||d||^2\}\\ s.t.\quad\nabla f_i(x_k)^Td\leq\alpha&\end{cases}\qquad (2)$
$(2)$式中引入了一个辅助变量$\alpha=\max_i\nabla f_i(x_k)^Td$，将最大化问题转化为一个不等式约束条件$\nabla f_i(x_k)^Td\leq\alpha$。通过引入辅助变量$\alpha$和约束条件，我们将原始的最大化-最小化问题转化为一个带有约束的优化问题，因此下面可以通过一些标准的优化算法如拉格朗日乘数法、KKT条件等来求解上述的约束优化问题。
优化理论基础
拉格朗日乘数法
拉格朗日乘数法是一种用于求解约束优化问题的数学方法。它通过引入拉格朗日函数，将约束条件与目标函数结合，从而将约束优化问题转化为无约束优化问题。
假设有如下优化问题，想要求目标函数的最小值
$\begin{aligned}&\min\quad f_{0}(x),x\in\mathbb{R}^{n}\\&s.t.\quad f_{i}\left(x\right)\leq0,\text{其中i}=1,2,3\ldots\mathrm{m}\end{aligned}$
则该问题的拉格朗日函数可以写为
$L(x,\lambda)=f_0(x)+\sum\lambda_if_i(x)$
然后我们可以通过求解该函数的极值点来找到原问题的解。下面给出一个直观的例子
蓝线代表目标函数，黄线代表约束条件，则图中的相切点就为所求约束问题的最小值。在切点处有$\nabla L(x,y)=0$，这是因为在切点处目标函数和约束函数的梯度方向一致，通过控制拉格朗日算子$\lambda$的大小，即可得到$\nabla L(x,y)=0$。因此由$\nabla L(x,y)=0$求解拉格朗日函数的极值极为原约束问题的解。上面是一个二元单约束条件的情况，下面是一个更复杂的多元多约束条件的情况。
该约束问题的解在图中表示为$x^*$，为了简化，图中只给出了$5$个约束条件。在极值点$x=x^*$处有
$\begin{aligned}&g_{\alpha}\left(x^{*}\right)=g_{\beta}\left(x^{*}\right)=0（边界条件）\\&\lambda_{\alpha}\nabla g_{\alpha}\left(x^{*}\right)+\lambda_{\beta}\nabla g_{\beta}\left(x^{*}\right)=-\nabla f\left(x\right)\Longrightarrow\lambda_{\alpha},\lambda_{\beta}\neq0（保证拉格朗日函数梯度为0）\end{aligned}$
而对于其他三个约束条件，有
$\begin{aligned}&\text{其他}g_i\left(x^*\right)<0,\\&\lambda_{i}\cdot\nabla g_{i}\left(x\right)=0\Rightarrow\lambda_{i}=0\left(i\neq\alpha,\beta\right)（保证拉格朗日函数梯度为0）\end{aligned}$
从图中可以看到，其他三个约束条件的梯度对$\nabla f(x)$实际上是没有起到约束作用的，因此可以得到下面一个结论
所有$\lambda_i\ge0$，$\begin{cases}如果\lambda_i=0，那么对应的约束条件g_i(x)是松弛的（不起作用的约束条件）\\ 如果\lambda_i>0，那么对应的约束条件g_i(x)是紧致的（起作用的约束条件）&\end{cases}$
还有下面一种特殊情况，即目标函数最小值$x=x^*$位于可行域之内，这种情况就相当于整个可行域都是松弛的，可以直接转换为无约束问题。
上述是拉格朗日乘数法几个较为直观的例子，然而拉格朗日乘数法存在一个问题，即拉格朗日函数求得的极值不一定是原目标函数的最值。这就引出了凸问题的概念。
凸集
一个集合$C\subseteq\mathbb{R}^n$是凸集，如果对于集合中的任意两点$x_1,x_2\in C$和任意$\lambda\in[0,1]$，它们的凸组合仍然属于$C$，即：
$\lambda x_1+(1-\lambda)x_2\in C,\quad\forall x_1,x_2\in C,\lambda\in[0,1]$
下面是一些常见的凸集
- 欧几里得空间
- 整个空间$\mathbb{R}^{n}$是凸集
- 超平面
- 超平面$\{x\in\mathbb{R}^n\mid a^\top x=b\}$是凸集
- 半空间
- 半空间$\{x\in\mathbb{R}^n\mid a^\top x\le b\}$是凸集
- 多面体
- 多面体$\{x\in\mathbb{R}^n\mid Ax\leq b\}$是凸集
- 单纯形
- 在几何学中，单纯形是最简单的多面体，由$n+1$个顶点在$n$维空间中的凸包构成，如
- $0$-单纯形——点（$0$维$1$点）、$1$-单纯形——线段（$1$维$2$点）、$2$-单纯形——三角形（$2$维$3$点）
- $n$-单纯形——$n$维空间中的超多面体，由$n+1$个顶点构成
之所以首先介绍凸集，是因为凸集有一些良好的性质
- 凸集的交集仍然是凸集
- 如果$C_1$和$C_2$是凸集,那么$C_1\cap C_2$也是凸集
- 这一性质可以推广到任意多个凸集的交集
- 凸集的仿射变换仍然是凸集
- 果$C$是凸集，$A$是矩阵，$b$是向量，则集合$\{Ax+b\mid x\in C\}$也是凸集
- 凸集的和集也是凸集
- 如果$C_1$ 和$C_2$是凸集，那么它们的和集$C_1+C_2=\{x_1+x_2\mid x_1\in C_1,x_2\in C_2\}$也是凸集。
- 凸包的凸性
- 任意集合的凸包（包含该集合的最小凸集）是凸集
凸包
给定一组点$P=\{p_1,p_2,\ldots,p_n\}$，凸包是包含所有这些点的最小凸集。在二维情况下，凸包是一个凸多边形，其顶点是$P$中的某些点，。在三维情况下，凸包是一个凸多面体。
凸包有以下性质
- 最小性：凸包是包含所有点的最小凸集，即不存在比凸包更小的凸集能够包含所有点。
- 唯一性：给定一组点，其凸包是唯一的。
- 边界：凸包的边界由点集中的某些点组成，这些点称为凸包的顶点。
凸组合
给定一组点$x_1,x_2,\ldots,x_n$和一组权重$\lambda_1,\lambda_2,\ldots,\lambda_n$，凸组合定义为
$y=\sum_{i=1}^n\lambda_ix_i$
其中权重$\lambda_i$满足
$\lambda_i\geq0\quad\text{且}\quad\sum_{i=1}^n\lambda_i=1$
点$x_i$可以是向量、标量或其他数学对象。凸组合的几何意义是点的加权平均，其中权重决定了每个点在组合中的贡献。凸组合的结果$y$位于点$x_1,x_2,\ldots,x_n$的凸包内。如果所有点$x_i$属于一个凸集，那么它们的凸组合$y$也属于该凸集。
单纯形
在数学中，单纯形可以通过凸组合来定义。给定$n+1$个仿射独立的点$v_0,v_1,\ldots,v_n$，单纯形$S$定义为这些点的凸组合
$\begin{aligned}S=\left\{\sum_{i=0}^n\lambda_iv_i\middle |\lambda_i\geq0,\sum_{i=0}^n\lambda_i=1\right\}\end{aligned}$
其中$\lambda_i$是权重系数，表示每个顶点在单纯形中的贡献。单纯形的维度由顶点的数量决定。
单纯形在优化中最重要的应用是单纯形法（Simplex Method），单纯形法是一种迭代算法用于求解线性规划问题
$\begin{aligned}&\max c^\top x\\&s.t.\;Ax\le b,\;x\ge0\end{aligned}$
单纯形法的核心思想是
- 线性规划问题的可行域是一个凸多面体（单纯形的推广）
- 最优解一定出现在可行域的顶点（单纯形的顶点）上
- 线性函数的性质决定了其极值（最大值或最小值）一定出现在可行域的边界上，而不是内部
- 如果可行域是一个凸多面体，极值一定出现在顶点上
- 单纯形法通过从一个顶点移动到相邻顶点，逐步逼近最优解
单纯形法的算法流程如下
- 初始化：找到一个初始可行解（顶点）
- 迭代：
- 检查当前顶点是否是最优解
- 如果不是，选择一个相邻顶点，使得目标函数值增加
- 终止：当找到最优解或确定问题无界时，停止迭代
凸函数
在机器学习中，凸函数是一类非常重要的函数，因为它们在优化问题中具有良好的性质，能够保证找到的局部最优解就是全局最优解。在优化理论中，与凸函数相对的为非凸函数。而在数学中，与凸函数相对的是凹函数。
一个函数$f:\mathbb{R}^n\to\mathbb{R}$是凸函数，如果对于定义域内的任意两点$x_1,x_2$和任意$\lambda\in[0,1]$，满足以下不等式。如果不等式是严格的（即严格$<$），则称$f$是严格凸函数
$f(\lambda x_1+(1-\lambda)x_2)\leq\lambda f(x_1)+(1-\lambda)f(x_2)$
凸集与凸函数的关系
凸集和凸函数之间有密切的联系
- 凸函数的下水平集是凸集：
- 如果$f$是凸函数，那么对于任意$\alpha\in\mathbb{R}$，集合$\{x\mid f(x)\leq\alpha\}$是凸集
- 这一性质常用于证明优化问题的可行域是凸集
- 凸优化问题的可行域是凸集：
- 凸优化问题中，目标函数是凸函数，约束条件是凸集，因此可行域是凸集
凸问题
凸问题在数学和机器学习中非常重要，因为凸问题具有良好的性质：能够保证找到的局部最优解就是全局最优解。一个优化问题被称为凸问题，如果它满足以下条件：
- 目标函数是凸函数
- 最小化问题中，目标函数$f(x)$是凸函数
- 最大化问题中，目标函数$f(x)$是凹函数
- 可行域是凸集：
- 不等式约束${g}_{i}(x)\leq0$中的函数${g}_{i}(x)$是凸函数
- 等式约束$h_j(x)=0$中的函数$h_j(x)$是仿射函数（即$h_j(x)=a_j^\top x+b_j$）
凸问题的一般形式可以写成
$\begin{aligned}\text{min}\;&f(x)\\s.t.\;&g_i(x)\leq0,\quad i=1,2,\ldots,m\\&h_j(x)=0,\quad j=1,2,\ldots,p\end{aligned}$
其中$f(x)$和 $g_i(x)$ 是凸函数，$h_j(x)$是仿射函数。
凸问题具有以下重要性质
- 局部最优解就是全局最优解
- 最优解的唯一性
- 如果目标函数是严格凸函数，那么最优解是唯一的
- 高效的求解方法
- 凸问题可以通过许多高效的算法求解，例如梯度下降法、牛顿法、内点法等
- 对偶性
- 凸问题通常具有强对偶性，即原问题和对偶问题的最优值相等
对偶问题
由于拉格朗日乘数法求出的极值不一定是最值，如下面一种非凸问题的情况
假如我们碰到了一个非凸问题，该怎么求解呢？我们可以看该非凸问题拉格朗日函数的对偶问题。假设有如下一般问题
$\begin{aligned}\text{min}\;&f_0(x),x\in\mathbb R^n\\s.t.\;&f_i(x)\leq0,\quad i=1,2,\ldots,m\\&h_i(x)=0,\quad i=1,2,\ldots,p\end{aligned}\qquad (p1)$
则通过拉格朗日乘数可以将该问题转换为如下问题形式
$L(x,\lambda,v)=f_{0}(x)+\sum\lambda_{i}f_{i}\left(x\right)+\sum\nu_{i}h_{i}\left(x\right)$
原问题：$\begin{aligned}&\min_{x}\max_{\lambda,\nu}L(x,\lambda,\nu)\\&s.t.\lambda\geq0\end{aligned}\qquad(p2)$
上述两个问题是等价的，问题$p1$的两个约束条件，实际上被转化到问题$p2$的中$\max_{\lambda,\nu}L(x,\lambda,\nu)$了。问题$p2$中$x$的可行域实际上是整个欧式空间$\mathbb R^n$。
下面针对问题$p2$中$x$的可行域进行分类讨论
$\begin{cases}x\text{不在可行域内:}&\max_{\lambda,\nu}L(x,\lambda,\nu)=f_0(x)+\infty+\infty=\infty\\x\text{在可行域内:}&\max_{\lambda,{\nu}}L({x},{\lambda},{\nu})=f_0({x})+0+0=f_0({x})\end{cases}$
优化内层最大化时，可暂时将外层最小化的$x$看作常数。当$p2$的$x$不在$p1$可行域内时，有$f_i(x)>0$，而对于$p2$有约束$\lambda\ge0$，因此$\lambda_{i}f_{i}\left(x\right)>0$，对$h_i(x)$也同理。因此$x$不在$p1$可行域内时，最大化$L$为$\infty$。
当当$p2$的$x$在$p1$可行域内时，恒有$f_i(x)\ge0,\;\lambda\le0\Longrightarrow\lambda_{i}f_{i}\left(x\right)\le0$，因此$x$在$p1$可行域内时，最大化$L$为$f_0(x)+0+0=f_0(x)$。
以上即证明了问题$p1$和问题$p2$有相同的最优解，即$p1$和$p2$等价。
上述原问题拉格朗日函数的对偶问题可以表示为如下，首先找到一个对偶函数
$对偶函数：g(\lambda,\nu)={\min}_{x}L(x,\lambda,\nu)$
$\begin{aligned}对偶问题：&\max_{\lambda,\nu}g(\lambda,\nu)=\max_{\lambda,\nu}\min_{x}L(x,\lambda,\nu)\\&s.t.\lambda\geq0\end{aligned}$
直观来看，实际就是把原问题的最小-最大问题转化为了对偶问题的最大-最小问题。
进一步来看，求对偶问题内层的一元最值$\min_x$可以转化为如下梯度约束
$\begin{aligned}对偶问题：\max_{\lambda,\nu}\;&g(\lambda,\nu)\\s.t.\;&\nabla_xL(x,\lambda,\nu)=0\\&\lambda\geq0\end{aligned}$
上述问题即为原问题的对偶问题。对偶问题有一个良好的特性，即不论原问题是什么，原问题的对偶问题是一个凸问题。下面给出证明。
假设原问题的拉格朗日函数如下
$L(x,\lambda,v)=f_{0}(x)+\sum\lambda_{i}f_{i}\left(x\right)+\sum\nu_{i}h_{i}\left(x\right)$
原问题的拉格朗日对偶函数如下
$g(\lambda,\nu)={\min}_{x}L(x,\lambda,\nu)$
可以进一步改写为，其中$x^\star$是常数
$g({\lambda},{\nu})=f_{0}(x^{\star})+\sum\lambda_{i}f_{i}(x^{\star})+\sum\nu_{i}h_{i}(x^{\star})$
这里$g({\lambda},{\nu})$确定的是一个线性超平面，其函数是一个凹凸函数（凸函数）。而对偶问题的可行域$\lambda\le0$半空间显然是一个凸集。因此该对偶问题一定是一个凸优化问题。
原问题与对偶问题的关系
弱对偶性
（弱对偶性）原问题得出的解一定大于等于对偶问题得到的解。
下面给出证明。假设原问题为
$\begin{aligned}原问题：&\min_{x}\max_{\lambda,\nu}L(x,\lambda,\nu)\\&s.t.\lambda\geq0\end{aligned}$
原问题的拉格朗日对偶问题为
$\begin{aligned}对偶问题：&\max_{\lambda,\nu}g(\lambda,\nu)=\max_{\lambda,\nu}\min_{x}L(x,\lambda,\nu)\\&s.t.\lambda\geq0\end{aligned}$
其中拉格朗日函数如下
$L(x,\lambda,v)=f_{0}(x)+\sum\lambda_{i}f_{i}\left(x\right)+\sum\nu_{i}h_{i}\left(x\right)$
首先对于任意固定的$\lambda$和$\nu$，拉格朗日函数可看作关于$x$的一元函数，其最小值满足
$\min_xL(x,\lambda,\nu)\leq L(x,\lambda,\nu)$
因为最大值不会减小函数的值，两边同时取最大值。
$\max_{\lambda,\nu}\min_xL(x,\lambda,\nu)\leq\max_{\lambda,\nu}L(x,\lambda,\nu)$
右边取最小值。此时左边已经是定值，而右边也可看作关于$x$的一元函数，因此有
$D^*=\max_{\lambda,\nu}\min_xL(x,\lambda,\nu)\leq\min_x\max_{\lambda,\nu}L(x,\lambda,\nu)=P^*$
其中$P^*$为原问题的解，$D^*$为对偶问题的解，因此原问题得出的解一定大于等于对偶问题得到的解$P^*\ge D^*$，这一性质也叫弱对偶性。
举个例子通俗来说，即“凤尾”$\ge$“鸡头”。何谓“凤尾”？我先选出最强的一批人$\max f$，然后组成实验班，实验班倒数第一就是$\min\;\max f$；何谓“鸡头”？我先选出最弱的一批人$\min f$，然后在这批比较弱的人当中选出最强的那个人，也即是$\max\;\min f$。
下面是一个直观的几何证明
首先是原始版本的原问题
$\begin{aligned}\text{min}\;&f_0(x),x\in\mathbb R^n\\s.t.\;&f_i(x)\leq0,\quad i=1,2,\ldots,m\\&h_i(x)=0,\quad i=1,2,\ldots,p\end{aligned}\qquad (p1)$
及其拉格朗日对偶问题
$\begin{aligned}对偶问题：&\max_{\lambda,\nu}g(\lambda,\nu)=\max_{\lambda,\nu}\min_{x}L(x,\lambda,\nu)\\&s.t.\lambda\geq0\end{aligned}$
下面我们对拉格朗日函数做一些简化（注意$h_i(x)=0$，但$h_i^\prime(x)$不一定为零）
$L(x,\lambda,v)=f_{0}(x)+\sum\lambda_{i}f_{i}\left(x\right){\color{lightgray}+\sum\nu_{i}h_{i}\left(x\right)}=\mathbf t+\mathbf{\lambda^T}\cdot \mathbf u$
其中$t$代表目标函数，$u$代表不等式约束，$\lambda$代表系数。这里$t,u$实际上都是向量，但为了简化，这里我们把它们看作变量（实际是关于x的函数）。则简化后，原问题的可行域可以表示为如下
$\{(t,\boldsymbol{u})|t=f_{0}(\boldsymbol{x}),u_{i}=f_{i}(\boldsymbol{x}),{\color{red}\boldsymbol{x}\in D}\}=G_{1}$
$D=\{x|f_i(x)\leq0, 其中i=1,2,\ldots,m,\;\;h_i(x)=0,其中 i=1,2,\ldots,q\}$
对偶问题的可行域如下
$\{(t,\boldsymbol{u})|t=f_0(\boldsymbol{x}),u_i=f_i(\boldsymbol{x}),{\color{red}\boldsymbol{x}\in\mathbb{R}^n}\}=G_2$
因此简化后拉格朗日原问题可以表示为如下形式
$\text{原问题:}\min_x\;\{t|(t,\boldsymbol{u})\in G_1,{\color{lightgray}u\leq0}\}$
对偶问题可以简化为如下
$\text{对偶问题:}\max_{\lambda}\min_x\;\{t+\lambda^T\cdot u|(t,\boldsymbol{u})\in G_2,{\color{red}\lambda\ge0}\}$
首先看下面的一般情况，其中$G_1+G_2$为对偶问题的可行域，$G_1$为原问题的可行域。显然这里的$P^*$就是原问题在可行域$G_1$下的解（$\min t$）
下面来看对偶问题的解，即$\max_{\lambda}\;\min_x t+\lambda^T\cdot u$，这里可以将$t+\lambda^T\cdot u$看作一条直线。先看内层的最小化，即最小化该直线的截距
下面再看外层的最大化$\max_{\lambda}$，相当于在满足最小化的情况下只调整直线斜率
最终找到对偶问题的解为$D^*$，显然这里满足$P^*\ge D^*$。
强对偶性
如果原问题是凸问题且满足某些约束条件（如 Slater 条件），则强对偶性成立
$g(\lambda^*,\nu^*)=f(x^*)$
即对偶问题的最优值等于原问题的最优值$P^*=D^*$。下面是一个强对偶的例子
Slater 条件
当原问题为凸问题，且满足如下的Slater条件时，强对偶性成立
$\begin{aligned}\text{Slater条件：}&存在一个点x\in relint\;D\\&使得f_i(x)<0,\quad其中i=1,2,3,\ldots,m,\;\;Ax=b\\&（relint\;D表示可行域D的相对内部）\end{aligned}$
这里$f_i(x)<0$表示原问题的不等式约束条件严格满足，$Ax=b$表示原问题的等式仿射约束精确满足。其中$x$位于可行域的相对内部，即非边界部分。Slater条件实际上保证了可行域不能退化为一点。如果等式约束$h_i(x)$不是仿射函数，Slater条件可能无法直接应用。
直观来看，如果将原问题转化为上述的$(t,u)$原问题，则Slater条件实际上保证了可行域在$u<0$的部分至少存在一点。
$\text{原问题:}\min_x\;\{t|(t,\boldsymbol{u})\in G_1,{\color{lightgray}u\leq0}\}$
Slater条件只是强对偶性的一个充分条件，也就是说一个强对偶问题不一定满足Slater条件。虽然目前仍不清楚强对偶问题的充要条件，但强对偶问题的必要条件是KKT条件，即一个强对偶问题一定满足KKT条件。当找到一个问题的最优点，则该点一定满足KKT条件，反之则不成立。
KKT条件（Karush-Kuhn-Tucker Conditions）
首先给出一般原凸优化问题，其中$f_0(x),f_i(x)$是凸函数，$h_i(x)$是仿射函数。
$\begin{aligned}\text{min}\;&f_0(x),x\in\mathbb R^n\\s.t.\;&f_i(x)\leq0,\quad i=1,2,\ldots,m\\&h_i(x)=0,\quad i=1,2,\ldots,p\end{aligned}$
其对偶问题如下
$\begin{aligned}对偶问题：\max_{\lambda,\nu}\;&g(\lambda,\nu)\\s.t.\;&\nabla_xL(x,\lambda,\nu)=0\\&\lambda\geq0\end{aligned}$
如果该凸优化问题是一个强对偶问题，则一定满足KKT条件。其中KKT条件包含以下五个子条件
$\begin{aligned}&\begin{cases}f_i(x)\le0\\h_i(x)=0\end{cases}\quad（解x必须满足原始问题的约束）&原问题可行条件\\\\&\begin{cases}\nabla_xL(x,\lambda,\nu)=0\\\lambda\geq0\end{cases}\quad（解x必须满足对偶问题的约束）&对偶可行条件\\\\&\lambda_if_i(x)=0&互补松弛条件\end{aligned}$
这里的互补松弛条件，实际上就是上面提到的松弛紧致约束的另一种写法，同时包含了松弛约束和紧致约束
当一个凸优化问题满足Slater条件时，该问题是一个强对偶问题，我们可以通过KKT条件来求解该问题的最优解。
使用KKT条件求解最优值
下面是一个具体的例子，原问题表述如下，其显然是一个凸优化问题，且满足Slater条件，因此是一个强对偶问题
$\begin{aligned}\text{min}\;&f_0(x)=x_1^2+x_2^2,x\in\mathbb R^n\\s.t.\;&f_1(x)=x_1+x_2-1\leq0,\\&h_1(x)=x_1-x_2=0\end{aligned}$
其拉格朗日函数如下
$\mathcal{L}(x,\lambda,\nu)=x_1^2+x_2^2+\lambda(x_1+x_2-1)+\nu(x_1-x_2)$
应用KKT条件如下
$\begin{aligned}&\begin{cases}x_1+x_2-1\leq0\\x_1-x_2=0\end{cases}\quad&原问题可行条件\\\\&\begin{cases}\frac{\partial\mathcal{L}}{\partial x_1}=2x_1+\lambda+\nu=0\\\frac{\partial\mathcal{L}}{\partial x_2}=2x_2+\lambda-\nu=0\\\lambda\geq0\end{cases}\quad&对偶可行条件\\\\&\lambda(x_1+x_2-1)=0&互补松弛条件\end{aligned}$
最终可以解得最优解为$f_0(0,0)=0$
多重梯度下降对偶问题
承接上文，我们已经将多重梯度下降问题改写为如下形式的约束问题
$\begin{cases}(d_k,\alpha_k)=\min\{\alpha+\frac{1}{2}||d||^2\}\\ s.t.\quad\nabla f_i(x_k)^Td\leq\alpha&\end{cases}$
其中$\alpha=\max_i\nabla f_i(x_k)^Td$。然而该问题不好直接求解，我们可以找到其拉格朗日对偶问题
首先引入该问题的拉格朗日函数
$L(d,\alpha,\lambda)=\alpha+\frac{1}{2}||d||^2+\sum_{i=1}^m\lambda_i(\nabla f_i(x_k)^Td-\alpha)$
对偶函数如下，即拉格朗日函数关于$d$和$\alpha$的下确界（最小化）
$g(\lambda)=\inf_{d,\alpha}L(d,\alpha,\lambda)$
使用KKT条件求解该最小优化问题，直接分别求偏导即可
$\frac{\partial L}{\partial\alpha}=1-\sum_{i=1}^m\lambda_i=0\Longrightarrow\sum_{i=1}^m\lambda_i=1$
$\frac{\partial L}{\partial d}=d+\sum_{i=1}^m\lambda_i\nabla f_i(x_k)=0\Longrightarrow d=-\sum_{i=1}^m\lambda_i\nabla f_i(x_k)$
然后将$d$和$\alpha$的表达式代入拉格朗日函数
$\begin{aligned}g(\lambda)=\inf_{d,\alpha}L(d,\alpha,\lambda)&=\alpha+\frac{1}{2}||d||^2+\sum_{i=1}^m\lambda_i(\nabla f_i(x_k)^Td-\alpha)\\&=\frac{1}{2}||d||^2+\sum_{i=1}^m\lambda_i\nabla f_i(x_k)^Td\\&=\frac{1}{2}\left\|-\sum_{i=1}^m\lambda_i\nabla f_i(x_k)\right\|^2+\sum_{i=1}^m\lambda_i\nabla f_i(x_k)^T\left(-\sum_{j=1}^m\lambda_j\nabla f_j(x_k)\right)\\&=\frac{1}{2}\left\|\sum_{i=1}^m\lambda_i\nabla f_i(x_k)\right\|^2-\left\|\sum_{i=1}^m\lambda_i\nabla f_i(x_k)\right\|^2\\&=-\frac{1}{2}\left\|\sum_{i=1}^m\lambda_i\nabla f_i(x_k)\right\|^2\end{aligned}$
对偶问题可以表示为最大化对偶函数
$\max_\lambda g(\lambda)=\max_\lambda\left(-\frac{1}{2}\left\|\sum_{i=1}^m\lambda_i\nabla f_i(x_k)\right\|^2\right)$
等价于最小化$\left\|\sum_{i=1}^m\lambda_i\nabla f_i(x_k)\right\|^2$，因此多重梯度下降问题的对偶问题可以表示成如下
$\begin{aligned}\arg \min_\lambda\;&\left\|\sum_{i=1}^m\lambda_i\nabla f_i(x_k)\right\|^2\\ s.t.&\;\sum_{i=1}^m\lambda_i=1,\quad\lambda_i\geq0\end{aligned}$
直观来看，就是寻找一组权重向量$\lambda$，使多目标函数梯度加权和的$L2$范数最小
多任务学习
多任务学习（Multi-Task Learning, MTL）是一种机器学习范式，旨在通过同时学习多个相关任务来提高模型的泛化能力和性能。与单任务学习不同，MTL通过共享任务之间的信息，利用任务之间的相关性来增强模型的学习效果。在多任务学习中，部分模型参数是多个任务共享的。这些共享参数捕捉任务之间的共同特征和结构。除了共享参数外，每个任务还有自己特定的参数，用于捕捉任务独有的特征。
Ozan Sener等人的研究表明，多任务学习本质是一个多目标优化问题。多任务学习的形式化定义如下
考虑一个多任务学习问题，输入空间为$\mathcal X$，任务集空间为${\mathcal{Y}^{t}}_{t\in[T]}$，给定一个包含$N$个个独立同分布数据点的数据集$\{x_{i},y_{i}^{1},\ldots,y_{i}^{T}\}_{i\in[N]}$，其中$N$表示任务个数，$y_i^t$是第$t$个任务的第$i$个数据点的标签。则第$t$个任务特征提取过程可以表示为
$f^t(\mathbf{x};\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^t):\mathcal{X}\to\mathcal{Y}^t$
其中$\boldsymbol{\theta}^{sh}$是任务共享参数，$\boldsymbol{\theta}^t$是第$t$个任务特有参数。每个任务的损失函数如下
$\mathcal{L}^{t}(\cdot,\cdot):\mathcal{Y}^{t}\times\mathcal{Y}^{t}\to\mathbb{R}^{+}$
多任务学习的目标是以下的经验风险最小化公式
$\begin{aligned}\min_{\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^1,\ldots,\boldsymbol{\theta}^T}\sum_{t=1}^Tc^t\hat{\mathcal{L}}^t(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^t)\end{aligned}$
其中$c^t$是每个任务的权重，$\hat{\mathcal{L}}^t(\theta^{sh},\theta^t)$是第$t$个任务的经验损失，定义如下
$\hat{\mathcal{L}}^t(\theta^{sh},\theta^t)\triangleq\frac{1}{N}\sum_i\mathcal{L}(f^t(x_i;\theta^{sh},\theta^t),y_i^t)$
这里第$t$个任务的经验损失代表了模型在所有数据点上的预测与真实标签之间的损失均值。
尽管加权求和公式十分直观，但它通常需要进行昂贵的网格搜索（grid search）来调整不同任务的权重，或者使用启发式方法搜索权重向量。加权求和的另外一个问题是难以定义全局最优性。如考虑两组解$\theta,\overline\theta$，对某些任务$t_1,t_2$同时有
$\hat{\mathcal{L}}^{t_{1}}(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^{t_{1}})<\hat{\mathcal{L}}^{t_{1}}(\bar{\boldsymbol{\theta}}^{sh},\bar{\boldsymbol{\theta}}^{t_{1}})$
$\hat{\mathcal{L}}^{t_{2}}(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^{t_{2}})>\hat{\mathcal{L}}^{t_{2}}(\bar{\boldsymbol{\theta}}^{sh},\bar{\boldsymbol{\theta}}^{t_{2}})$
此时$\theta$在任务$t_1$中表现更好，$\bar\theta$在任务$t_2$中表现更好。在不知道任务之间相对重要性的情况下，无法比较这两组解哪个更好。
因此作者将一个多任务学习MTL问题看作一个多目标优化问题：优化一组可能相互冲突的目标函数。首先使用向量值损失函数$\mathbf L$形式化定义MTL的多目标优化形式
$\begin{aligned}\min_{\theta^{sh},\theta^1,\ldots,\theta^T}\mathbf L(\theta^{sh},\theta^1,\ldots,\theta^T)=\min_{\theta^{sh},\theta^1,\ldots,\theta^T}\left(\hat{\mathcal{L}}^1(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^1),\ldots,\hat{\mathcal{L}}^T(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^T)\right)^{\mathrm T}\end{aligned}$
多目标优化的目标是达到帕累托最优（Pareto optimality）。
MTL下的帕累托最优（Pareto optimality）
$\textbf{(定义1. \;\;帕累托支配)}$ 对于任意的两个解$\theta,\bar\theta\in\Omega$，解$\theta$支配解$\bar\theta$时，记作$\theta\prec\bar{\theta}$，则对于所有的任务$t$有
$L^i(\theta^\mathrm{sh},\theta^i)\leqslant L^i(\bar{\theta}^\mathrm{sh},\bar{\theta}^i),\forall i\in(1,2,\cdots,T),$
且$L^{j}(\theta^{\mathrm{sh}},\theta^{j})<L^{j}(\bar{\theta}^{\mathrm{sh}},\bar{\theta}^{j}),\exists j\in(1,2,\cdots,T)$
$\textbf{(定义2. \;\;帕累托最优解)}$ 如果不存在解$\theta(\theta\in\Omega)$使得$\theta\prec{\theta}^*$，则称解$\theta^*$为Pareto最优解。所有Pareto最优解构成的集合称为Pareto集$\mathcal{P}_{\theta}$, Pareto集中所有Pareto最优解在目标空间的映射形成的解集组成Pareto最优解的目标向量值集合, 该集合称为Pareto前沿$\mathcal{P}_{\mathbf{L}}={\mathbf{L}(\boldsymbol{\theta})}_{\boldsymbol{\theta}\in\mathcal{P}_{\boldsymbol{\theta}}}$。帕累托前沿表示在多目标优化中所有可能的帕累托最优解在损失空间中的分布。
多重梯度下降算法（Multiple Gradient Descent Algorithm, MGDA）
与单目标优化类似，多目标优化也可以通过梯度下降来求解局部最优解。上文已经分析过，可以使用KKT条件来求解该问题。在多任务学习MTL场景下，对于任务特定参数和共享参数，KKT条件如下（可分别看作多任务最优和单任务最优）
$\begin{aligned}&存在\alpha^{1},\ldots,\alpha^{T}\geq0，使得\sum_{t=1}^{T}\alpha^{t}=1且\sum_{t=1}^{T}\alpha^{t}\nabla_{\boldsymbol{\theta}^{sh}}\hat{\mathcal{L}}^{t}(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^{t})=0\\&对所有任务t有\nabla_{\boldsymbol{\theta}^t}\hat{\mathcal{L}}^t(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^t)=0\end{aligned}$
任何满足这些条件的解被称为帕累托稳定点（Pareto stationary point）。每个帕累托最优点都是帕累托稳定点，但反之则不一定成立。
考虑以下优化问题，实际上就是多目标优化的对偶问题，上文已经推导过
$\begin{aligned}\min_{\alpha^{1},…,\alpha^{T}}\left\{\left\|\sum_{t=1}^{T}\alpha^{t}\nabla_{\boldsymbol{\theta}^{sh}}\hat{\mathcal{L}}^{t}(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^{t})\right\|_{2}^{2}\;\;\middle|\;\;\sum_{t=1}^{T}\alpha^{t}=1,\alpha^{t}\geq0\quad\forall t\right\}\end{aligned}\qquad(p1)$
Désidéri等证明了上述优化问题的解以下有两种情况
- 这个优化问题的解为是0，此时得到的解满足KKT条件
- 得到的解提供了所有任务的下降方向
MGDA的求解
求解问题$p1$等价于在输入点的凸包中找到最小范数点。在计算几何中，该问题等价于在凸包中找到与给定查询点最近的点。然而以往计算几何领域的研究并不适用于MTL场景。在计算几何文献中，算法通常处理的是在低维空间（通常是2维或3维）中大量点的凸包中找到最小范数点的问题。在MTL场景下，点的数量是任务的数量通常较少，而维度是共享参数的数量可能达到数百万。因此作者采用了一种基于凸优化的方法。
两任务的情况
在考虑一般情况之前，首先考虑两任务优化的情况
$\begin{aligned}\min_{\alpha\in[0,1]}\left\|\alpha\nabla_{\theta^{sh}}\hat{\mathcal{L}}^1(\theta^{sh},\theta^1)+(1-\alpha)\nabla_{\theta^{sh}}\hat{\mathcal{L}}^2(\theta^{sh},\theta^2)\right\|_2^2\end{aligned}$
简化为
$\begin{aligned}\min_{\alpha\in[0,1]}\left\|\alpha\theta+(1-\alpha)\bar{\theta}\right\|_2^2\end{aligned}\qquad(p2)$
其中$\theta$表示$\nabla_{\theta^{sh}}\hat{\mathcal{L}}^1(\theta^{sh},\theta^1)$，$\bar{\theta}$表示$\nabla_{\theta^{sh}}\hat{\mathcal{L}}^2(\theta^{sh},\theta^2)$。
对问题$p2$进行求导取求最值。首先展开$p2$
$\begin{aligned}\left\|\alpha\theta+(1-\alpha)\bar{\theta}\right\|_2^2&=(\alpha\theta+(1-\alpha)\bar{\theta})^\top(\alpha\theta+(1-\alpha)\bar{\theta})\\&=\alpha^2\theta^\top\theta+(1-\alpha)^2\bar{\theta}^\top\bar{\theta}+2\alpha(1-\alpha)\theta^\top\bar{\theta}\\&=\alpha^2\left\|\theta\right\|_2^2+(1-\alpha)^2\left\|\bar{\theta}\right\|_2^2+2\alpha(1-\alpha)\theta^\top\bar{\theta}=f(\alpha)\end{aligned}$
对$f(\alpha)$进行求导并令其等于零
$\frac{df(\alpha)}{d\alpha}=2\alpha\left\|\theta\right\|_2^2-2(1-\alpha)\left\|\bar{\theta}\right\|_2^2+2(1-2\alpha)\theta^\top\bar{\theta}=0$
得到
$\alpha\left\|\theta\right\|_2^2-(1-\alpha)\left\|\bar{\theta}\right\|_2^2+(1-2\alpha)\theta^\top\bar{\theta}=0$
$\alpha(\left\|\theta\right\|_2^2+\left\|\bar{\theta}\right\|_2^2-2\theta^\top\bar{\theta})=\left\|\bar{\theta}\right\|_2^2-\theta^\top\bar{\theta}$
最终解得$\alpha$
$\begin{aligned}\alpha&=\frac{\left\|\bar{\theta}\right\|_2^2-\theta^\top\bar{\theta}}{\left\|\theta\right\|_2^2+\left\|\bar{\theta}\right\|_2^2-2\theta^\top\bar{\theta}}\\&=\frac{\left\|\bar{\theta}\right\|_2^2-\theta^\top\bar{\theta}}{\left\|\theta-\bar{\theta}\right\|_2^2}\\&=\frac{\left(\bar\theta-\theta\right)^\top\bar\theta}{\left\|\theta-\bar{\theta}\right\|_2^2}\end{aligned}$
由于约束条件，$\alpha\in[0,1]$，因此需要对解进行裁剪
- 如果$\alpha<0$，则取$\alpha=0$
- 如果$\alpha>1$，则取$\alpha=1$
因此最终两任务优化解析解为
$\begin{aligned}&\alpha=\begin{cases}0,&\mathrm{if~}\theta^\top\bar{\theta}\geq\left\|\theta\right\|_2^2,\\\frac{||\bar{\theta}||_2^2-\theta^\top\bar{\theta}}{||\theta-\bar{\theta}||_2^2},&\mathrm{if~}\theta^\top\bar{\theta}<||\theta||_2^2\;\mathrm{and~}\;\theta^\top\bar{\theta}<||\bar{\theta}||_2^2,\\1,&\mathrm{if~}\theta^\top\bar{\theta}\geq\left\|\bar{\theta}\right\|_2^2.&\end{cases}\end{aligned}$
上述解析解的几何意义如下
- 当$\theta^\top\bar{\theta}\geq||\theta||_2^2$时，任务1的梯度$\theta$与任务2的梯度$\bar\theta$的方向非常接近，此时$\alpha=0$，即完全依赖任务2
- 当$\theta^\top\bar{\theta}<||\theta||_2^2\;\mathrm{and~}\;\theta^\top\bar{\theta}<||\bar{\theta}||_2^2$时，任务1和任务2的梯度方向不一致，此时$\alpha$取中间值平衡两个任务的梯度
- 当$\theta^\top\bar{\theta}\leq||\theta||_2^2$时，任务2的梯度$\bar\theta$与任务1的梯度$\theta$的方向非常接近，此时$\alpha=1$，即完全依赖任务1
多任务的情况
上述是任务数$n=2$的情况，当任务数$n>2$时可以通过Frank-Wolfe算法将问题转化为多个$n=2$的情况进行迭代。
其中MTL的参数更新流程如下
- $\textbf{for}\;t=1\;\textbf{to}\;T\;\textbf{do}$
- $\quad\theta^t=\theta^t-\eta\nabla_{\theta_t}\hat{\mathcal {L}}^t(\theta^{sh},\theta^t)$
- $\textbf{end for}$
- $\alpha^1,\ldots,\alpha^T=\textbf{Frank-Wolfe-Solver}(\theta)$
- $\theta^{sh}=\theta^{sh}-\eta\sum^T_{t=1}\alpha^t\nabla_{\theta^{sh}}\hat{\mathcal {L}}^t(\theta^{sh},\theta^t)$
首先使用梯度下降循环更新任务特定参数$\theta^t$，然后通过Frank-Wolfe算法求解权重寻找一个共同的下降方向，最后通过梯度下降沿着一个共同的下降方向更新共享权重。
Frank-Wolfe算法
Frank-Wolfe算法（也称为条件梯度法，Conditional Gradient Method）是一种用于求解带约束的凸优化问题的迭代算法。Frank-Wolfe算法的核心思想是通过在每次迭代中线性化目标函数，并在约束集上求解线性规划问题来找到一个可行的下降方向，然后沿着这个方向进行一维搜索来更新解。
Frank-Wolfe算法的主要步骤如下
- 线性化目标函数：
- 在当前点$x_k$处，对目标函数$f(x)$进行线性近似：
$f(x)\approx f(x_k)+\nabla f(x_k)^\top(x-x_k)=f(x_k)-\nabla f(x_k)^\top x_k+\nabla f(x_k)^\top x$ - 线性化后的目标函数是$x$的线性函数
- 在当前点$x_k$处，对目标函数$f(x)$进行线性近似：
- 求解线性规划问题：
- 在约束集$D$上，求解线性化后的目标函数的最小值
$\begin{aligned}s_k=&\arg\min_{s}\nabla f(x_k)^\top s\\&s.t.\;s\in D\end{aligned}$ - 这个步骤通常比直接求解原问题简单，因为线性规划问题有高效的求解方法
- 在约束集$D$上，求解线性化后的目标函数的最小值
- 确定下降方向：
- 下降方向为$d_k=s_k-x_k$，即从当前点$x_k$指向线性规划问题的最优解$s_k$
- 一维搜索：
- 沿着下降方向$d_k$进行一维搜索，找到最优步长$\gamma_k$
$\begin{aligned}\gamma_k=&\arg\min_{\gamma}f(x_k+\gamma d_k)\\&s.t.\;\gamma\in [0,1]\end{aligned}$ - 更新当前点$x_{k+1}=x_k+\gamma_kd_k$
- 沿着下降方向$d_k$进行一维搜索，找到最优步长$\gamma_k$
- 迭代：
- 重复上述步骤，直到满足收敛条件（如梯度足够小或迭代次数达到上限）
Frank-Wolfe算法只需要求解线性规划问题，而不需要投影操作（Projection）。当约束集$D$是简单的凸集（如单纯形、球等）时，线性规划问题可以高效求解，因此Frank-Wolfe算法适用于大规模优化问题。
但Frank-Wolfe算法的收敛速度通常是次线性的（sublinear），尤其是在接近最优解时，收敛速度会变慢。算法的性能可能对初始点$x_0$的选择敏感，尤其是在非强凸目标函数的情况下。
Frank-Wolfe算法在MGDA中的应用
在MGDA中，Frank-Wolfe算法用于求解多任务学习中的共享参数优化问题，目标是找到一个能够平衡多个任务损失的下降方向，也即找到一组$\alpha=(\alpha^1,\alpha^2,\ldots,\alpha^T)$，使得
$\text{最优更新方向}=\sum_{t=1}^T\alpha^t\nabla_{\theta^{sh}}L^t(\theta^{sh},\theta^t)$
$\textbf{Frank-Wolfe-Solver}$具体流程如下
- 计算各任务损失和共享参数梯度：
- 计算各任务的损失函数$\hat{\mathcal{L}}^t(\theta^{sh},\theta^t)$，及各任务在共享参数上的梯度$\nabla_{\theta^{sh}}\hat{\mathcal{L}}^t(\theta^{sh},\theta^t)$
- $\nabla_{\theta^{sh}}\hat{\mathcal{L}}^t(\theta^{sh},\theta^t)$指示了各任务在共享参数上的下降情况，从而确定下一步如何更新参数$\theta^{sh}$
- 初始化任务权重：
- 均匀初始化所有任务的权重为$\alpha=(\alpha^{1},\ldots,\alpha^{T})=(\frac{1}{T},\ldots,\frac{1}{T})$
- 初始时，所有任务的权重相同，表示没有先验知识表明某个任务更重要。随着算法的迭代，权重会根据任务的梯度信息进行调整。
- 计算梯度矩阵：
- 计算所有损失函数关于共享参数的梯度矩阵$M$，其中$M_{i,j\in[0,T]}=(\nabla_{\theta^{sh}}\hat{\mathcal{L}}^i(\theta^{sh},\theta^i))^T(\nabla_{\theta^{sh}}\hat{\mathcal{L}}^j(\theta^{sh},\theta^j))$
- 其中每个元素$M_{i,j}$是任务$i$和任务$j$的共享参数梯度的内积，在一些论文中也称其为“任务亲和度”
- 任务亲和度衡量了两个任务之间是否冲突，当任务亲和度为负时说明梯度方向夹角为钝角，两个任务是冲突的，反之则不冲突
- 梯度矩阵$M$衡量了所有任务两两之间的任务亲和度。通过分析$M$，可以找到能够平衡多个任务损失的下降方向
- 计算最优索引：
- 计算共享参数梯度矩阵$M$所对应的最优索引$\hat{t}=\arg\min_{\gamma}\sum_{t}\alpha^{t}M_{\gamma t}$
- 这一步的目的是找到一个最优任务索引$\hat t$，其梯度方向能够最大程度地减少所有任务的加权损失
- 线性搜索：
- 基于两任务情况的解析解进行线性搜索$\hat{\gamma}=\arg\min_\gamma((1-\gamma)\alpha+\gamma M_{\hat t})^TM((1-\gamma)\alpha+\gamma M_{\hat t})$
- 线搜索是为了确定在当前方向$M_{\hat t}$上，参数更新的最佳步长$\hat\gamma$，以确保目标函数能够快速收敛
- 更新权重$\alpha$：
- 基于最优步长$\hat\gamma$更新权重$\alpha=(1-\hat{\gamma})\alpha+\hat{\gamma}M_{t}$
- 更新权重可以逐步调整每个任务对共享参数的影响，使得优化过程能够更好地平衡多个任务
- 判断收敛：
- 循环步骤$\textbf{4-6}$，当达到迭代次数上限，或者更新步长趋于零时$\hat\gamma\sim 0$停止迭代
- 返回任务权重$\alpha^1,\ldots,\alpha^T$
这里对$\textbf{步骤5}$线性搜索的计算公式做一下推导。首先MGDA可以看作以下优化问题
$\begin{aligned}\min_{\alpha^{1},…,\alpha^{T}}\left\{\left\|\sum_{t=1}^{T}\alpha^{t}\nabla_{\boldsymbol{\theta}^{sh}}\hat{\mathcal{L}}^{t}(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^{t})\right\|_{2}^{2}\;\;\middle|\;\;\sum_{t=1}^{T}\alpha^{t}=1,\alpha^{t}\geq0\quad\forall t\right\}\end{aligned}\qquad(p1)$
其目标函数可以表示为如下形式
$\begin{aligned}f(\alpha)=\left\|\sum_{t=1}^{T}\alpha^{t}\nabla_{\boldsymbol{\theta}^{sh}}\hat{\mathcal{L}}^{t}(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^{t})\right\|_{2}^{2}\end{aligned}$
进一步改写
$\begin{aligned}f(\alpha)&=\left\|\sum_{t=1}^{T}\alpha^{t}\nabla_{\boldsymbol{\theta}^{sh}}\hat{\mathcal{L}}^{t}(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^{t})\right\|_{2}^{2}\\&=\left(\sum_{t=1}^T\alpha^t\nabla_{\theta^{sh}}\hat{\mathcal L}^t(\theta^{sh},\theta^t)\right)^\top\left(\sum_{t=1}^T\alpha^t\nabla_{\theta^{sh}}\hat{\mathcal L}^t(\theta^{sh},\theta^t)\right)\\&=\left(\nabla_{\theta^{sh}}\hat{\mathcal L}^i(\theta^{sh},\theta^t)\alpha\right)^\top\left(\nabla_{\theta^{sh}}\hat{\mathcal L}^j(\theta^{sh},\theta^t)\alpha\right)\\&=\alpha^\top\left(\nabla_{\theta^{sh}}\hat{\mathcal L}^i(\theta^{sh},\theta^t)\right)^\top\left(\nabla_{\theta^{sh}}\hat{\mathcal L}^j(\theta^{sh},\theta^t)\right)\alpha\\&=\alpha^\top M\alpha\end{aligned}$
因此MGDA实际上是一个带有线性约束的凸二次型问题。其中两任务优化问题是上面问题解的特例。
MGDA最终算法流程
通过上面的分析，我们能够得到MGDA算法的完整流程
- 算法名称：$\textbf{MGDA}$
- 算法输入：学习率$\eta$，迭代终止条件$\textbf S$，任务集合$\{T_t\}$
- 算法输出：任务共享参数$\theta^{sh}$，任务特定参数$\theta^t$
- 算法流程：
- $\textbf{for}\;t=1\;\textbf{to}\;T\;\textbf{do}$
- $\quad\theta^t=\theta^t-\eta\nabla_{\theta_t}\hat{\mathcal {L}}^t(\theta^{sh},\theta^t)\qquad（循环更新任务特定参数）$
- $\textbf{end for}$
- $\textbf {procedure}\quad\textbf{Frank-Wolfe-Solver}(\theta)$
- $\quad$均匀初始化任务权重$\alpha=(\alpha^{1},\ldots,\alpha^{T})=(\frac{1}{T},\ldots,\frac{1}{T})$
- $\quad$计算梯度矩阵$M$，其中$M_{i,j\in[0,T]}=(\nabla_{\theta^{sh}}\hat{\mathcal{L}}^i(\theta^{sh},\theta^i))^T(\nabla_{\theta^{sh}}\hat{\mathcal{L}}^j(\theta^{sh},\theta^j))$
- $\quad\textbf{repeat}$
- $\qquad$计算共享参数梯度矩阵$M$所对应的最优索引$\hat{t}=\arg\min_{\gamma}\sum_{t}\alpha^{t}M_{\gamma t}$
- $\qquad$线性搜索$\hat{\gamma}=\arg\min_\gamma((1-\gamma)\alpha+\gamma M_{\hat t})^TM((1-\gamma)\alpha+\gamma M_{\hat t})$
- $\qquad$更新权重$\alpha=(1-\hat{\gamma})\alpha+\hat{\gamma}M_{t}$
- $\quad\textbf{until}\;\textbf{S}$
- $\quad\textbf {return}\;\alpha^{1},\ldots,\alpha^{T}$
- $\textbf {end procedure}$
- ${\theta}^{sh}={\theta}^{sh}-\eta\sum_{t=1}^T\alpha^t\nabla_{{\theta}^{sh}}\hat{\mathcal{L}}^t({\theta}^{sh},{\theta}^t)\qquad（更新共享权重）$
- $\textbf{return}\;\theta^t,\theta^{sh}$
针对Encoder-Decoder结构的MGDA优化
上文提到的MGDA算法适用于任何基于梯度下降的优化问题。有实验表明，Frank-Wolfe算法高效且准确，通常能够在较少的迭代次数内收敛，并且对训练时间的影响可以忽略不计。然而在MTL场景下，算法需要为每个任务$t$计算共享参数的梯度$\nabla_{{\theta}^{sh}}\hat{\mathcal{L}}^t({\theta}^{sh},{\theta}^t)$，此时需要对每个任务进行一次反向传播。由于反向传播的计算通常比前向传播更昂贵，这导致训练时间随任务数量$T$线性增长，因此对于任务数量较多的问题来说开销过大。
针对上述问题，Ozan Sener等对MGDA做了进一步优化，提出了MGDA-UB算法（MGDA-Upper Bound）。该算法通过优化目标函数的上界，只需要一次反向传播便能高效地更新共享参数$\theta^{sh}$。并且作者进一步证明，在合理的假设下，优化该上界可以得到Pareto最优解。
编码器-解码器架构
编码器-解码器架构结合了共享的表示函数和任务特定的决策函数。这类架构涵盖了大多数现有的多任务学习模型。其形式化定义如下
$f^t(\mathbf{x};\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^t)=(f^t(\cdot;\boldsymbol{\theta}^t)\circ g(\cdot;\boldsymbol{\theta}^{sh}))(\mathbf{x})=f^t(g(\mathbf{x};\boldsymbol{\theta}^{sh});\boldsymbol{\theta}^t)$
其中$g$代表任务共享的表示函数，$f^t$是任务特定的函数，它们以共享表示作为输入。下面进一步将共享表示写为如下形式
$\begin{aligned}&\mathbf{Z}=(\mathbf{z}_1,\ldots,\mathbf{z}_N)\\&s.t.\;\mathbf{z}_i=g(\mathbf{x}_i;\boldsymbol{\theta}^{sh})\end{aligned}$
上界推导
根据链式法则，我们可以得到原优化问题的上界
$\begin{aligned}\left\|\sum_{t=1}^T\alpha^t\nabla_{\boldsymbol{\theta}^{sh}}\hat{\mathcal{L}}^t(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^t)\right\|_2^2\leq\left\|\frac{\partial\mathbf{Z}}{\partial\boldsymbol{\theta}^{sh}}\right\|_2^2\left\|\sum_{t=1}^T\alpha^t\nabla_\mathbf{Z}\hat{\mathcal{L}}^t(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^t)\right\|_2^2\end{aligned}$
其中$\left\|\frac{\partial\mathbf{Z}}{\partial\boldsymbol{\theta}^{sh}}\right\|_2$表示$\boldsymbol Z$对共享参数$\boldsymbol\theta^{sh}$的雅可比矩阵的范数。$\nabla_\mathbf{Z}\hat{\mathcal{L}}^t(\boldsymbol{\theta}^{sh},\boldsymbol{\theta}^t)$是任务$t$损失函数对表示$\boldsymbol Z$的梯度。