做为最后一篇分布式多任务学习的论文阅读记录，我决定对我目前为止粗读和精读的论文进行一次总结，然后陈述一些个人对该研究领域的见解和想法。目前已经有许多论文对多任务学习提出了并行化策略，我们可以大致概括如下几类：(1) 基于近端梯度的同步算法 (2) 基于近端梯度的异步算法 (3) 基于分解代理损失函数的算法 (4) 基于本地去偏估计的算法。⽬前关于不同的损失函数和不同的正则项已经有很多学者做过了，不过⽬前基于任务簇/层次化的多任务学习⽅法还没有⼈对专门其并⾏化。
做为最后一篇分布式多任务学习的论文阅读记录，我决定对我目前为止粗读和精读的论文进行一次总结，然后陈述一些个人对该研究领域的见解和想法。
1. 论文总结归纳
目前已经有许多论文对多任务学习提出了分布式并行方案。在分布式多任务学习中，传统的处理方式[1][2][3]仍然是基于主从节点策略（server-client strategy）：多个任务节点分摊任务，然后将信息交给主节点汇总（比如在分布式近端映射算法中，任务节点进行梯度计算，主节点负责近端映射）。
但中心化模式自身存在弊端。首先，当网络传输代价比较大时，容易在中心节点处形成瓶颈；其次，中心化方法对系统的稳定性要求高，因为它要求中心节点能够稳定地聚合和分发模型，一旦中心节点出错，整个任务必然失败;最后，在某些现实场景中，任务节点只存在和其相邻节点的网络连接，这时中心化算法将无法工作。
基于以上中心化分布式学习算法的弊端，分布式多任务学习也越来越朝着去中心化的路线发展[4][5][6][7]，也就是强调任务节点只能和其邻接点相互通信，而不存在存放全局模型的一个主节点。加之近年来联邦学习的发展，该领域往往会关注任务节点的数据隐私性，以及一些分布式计算中的经典问题，比如拜占庭容错等。此外，由于在现实应用场景中任务之间的关系是未知的（并非做为一个先验），而且出于对流数据的使用、低计算开销的需求和对变化环境更强的适应性的考虑，常常需要引入在线学习。
因此分布式多任务学习也常常和在线学习结合。在线多任务学习中任务之间的邻接权重矩阵可以表示任务之间的关系，而该权重也可以实时跟随任务之间的参数距离或梯度变化程度来动态调整。
注1: 分布式多任务学习和联邦学习的区别
在标准的联邦学习中，每个节点任务不共享数据，但是可以共享参数，以此联合训练出各一个全局的模型。也就是说，联邦学习下每个节点的任务是一样的（但是由于数据不独立同分布，每个模型训练出的局部模型差异会很大，就会使得构建一个全局的、通用的模型难度很大。比如同样一个下一个单词预测的任务，同样给定"I love eating,"，但对于下一个单词每个client会给出不同的答案，这也是现在有人提出联邦多任务学习的原因）。
为了解决联邦学习中数据不独立同分布的的问题，有论文[7][15]提出不求训练出一个全局的模型，使每个节点训练各不相同的模型这样一种训练方式，这被冠名为联邦多任务学习了。
注2: 分布式多任务学习和联邦多任务学习的区别
此二者非常相似，但是联邦多任务学习可以看做是分布式多任务学习在特殊条件下的限制版，即联邦多任务学习中可能更关注节点的容错性，以及节点数据集隐私（节点之间的数据不能共享），单纯的分布式多任务学习一般没这几个需求。此外还有一点就是，按照最初的传统联邦多任务学习一般是有中心节点的(如论文[34]中所说)，而分布式多任务学习是可以去中心化的（如论文[10]中所说）。但是也有论文把联邦多任务学习也去中心化了([35])，所以这个应该算不上主要依据。
下面我就按照中心化和去中心化这两个类别对现有分布式并行方式进行归纳总结。
1.1 中心化方法（centralized approach）
(1) 基于近端梯度的同步算法
描述 多任务学习优化中首先面临的问题即目标函数\(F(\bm{\theta}) = f(\bm{\theta}) + g(\bm{\theta})\)中正则项\(g(\bm{\theta})\)的非凸性，而在数值优化里面近端梯度算法[8]（包括一阶的FISTA（近端梯度算法的一种变种）、SpaRSA和最近提出的二阶的PNOPT）可以有效求解这种所谓的复合凸目标函数。而近端梯度算法一般分为\(f(\bm{\theta})\)的梯度计算和近端映射两个步骤。\(f(\bm{\theta})\)的梯度计算可以很容易地分摊到各个任务节点上（每个任务节点负责计算一个任务对应的梯度）；\(g(\bm{\theta})\)的计算不易分解，可以由主节点完成，即待所有任务节点运算完毕后，将梯度传往主节点后汇集，并在此基础上对权重矩阵进行近端映射，以得到更新后的参数矩阵。最后，主节点又将更新了的参数向量分发给各任务节点，开始下一轮迭代。
优点 算法逻辑简单清晰且通用性强，几乎可以推广到所有基于正则化的多任务学习。
缺陷 因为是基于同步通信的优化算法，如果有节点传输带宽过低（或直接down）掉，就会拖累整个系统的运行，导致不能容忍的运行时间和运算资源的浪费。
(2) 基于近端梯度的异步算法
描述 中心节点只要收到了来自一个任务节点的已经算好的梯度，就会马上对模型的参数矩阵进行更新，而不用等待其他任务节点完成计算[1]。特别地，在论文[1]中采用了一种前向-后向算子分裂的视角[9][10]来求解目标函数（其实就是近端梯度法，但采用算子的视角可以抽象为不动点迭代，方便我们后面结合KM算法），且最终的迭代方法采用论文[11]中讨论的经过异步坐标更新改造的KM迭代方法。
优点 因为通信是异步的，可以提高系统的吞吐率。
缺陷 如果对内存的读取不加锁的话会导致不一致性（inconsistency）问题，可能降低算法整体的收敛速率。
(3) 基于分解代理损失函数的算法
描述 对于形如\(F(\bm{\theta}) = f(\bm{\theta}) + g(\bm{\theta})\)的复合目标函数，FISTA算法[12]采取的策略是在迭代过程中不断构建代理损失函数\(Q_{\mathcal{L}}(\bm{\theta}, \hat{\bm{\theta}})\)，然后通过优化该代理损失函数来更新参数。后面我们发现，对该代理损失函数的求解进行并行化较为容易。在论文《Parallel Multi-Task Learning》[13]中则更进一步，首先将原始的\(F(\bm{\theta}) = f(\bm{\theta}) + g(\bm{\theta})\)问题先转换为了对偶问题，然后用FISTA算法对对偶问题进行迭代求解，在求解的过程中构建代理损失函数，然后对代理损失函数进行并行化。
优点 对代理损失函数可以按照固定的套路进行分解，从而使该方法具有较强的通用性。
缺陷 如果代理损失函数构建不恰当，则可能导致其做为原损失函数的上界过松，降低优化效果。而且论文只是将原问题分解为了子问题，然而子问题的求解仍然是串行的，可能会花费较多时间。
(4) 基于本地去偏估计的算法
描述 基于近端梯度的常规优化算法会带来较大的通信开销，但如果完全不通信就会退化为单任务学习。为了解决这个难点，论文《distributed multitask learning》[14]提出了基于去偏lasso的分布式算法。该算法适用于解决形如\(F(\bm{\theta}) = f(\bm{\theta}) + \text{pen}(\bm{\theta})\)的问题，其中\(\text{pen}(\bm{\theta})\)是group sparse 正则项。该算法介于常规的通信算法和不通信的算法之间，只需要一轮通信，但仍然保证了使用group regularization所带来的统计学效益。
优点 直接在保证多任务学习特性的条件下，大大减少了分布式计算所带来的的通信次数，是所有方法中加速效果最好的。
缺点 仅局限于基于group sparse正则项的多任务学习，难以进一步推广。
1.1 去中心化方法（decentralized approach）
(1) 用任务信息共享解决在线多任务学习的帕累托最优问题
描述 去中心化的在线多任务学习会面临帕累托（Pareto optimality）最优问题（即每个任务的最优解不同，最终只能折中达到一个全局最优，而这个全局最优会牺牲每个任务的精度），Zhang C[4]等人提出了一个基于任务信息共享的去中心化优化方法。在该方法中，每个任务节点都有机会负责所有的任务（存储有所有任务的权重）。每轮迭代之前每个节点会和相邻的节点做权重组合（去中心化方法中的一个常见操作，用于收敛到一个全局最小），然后每个任务随机接收另一个任务的数据，再根据此数据更新本地对应部分的权重。
优点 打破分布式多任务学习中的常规，创新性地提出了任务间的数据共享，有利于收敛到全局最优。
缺陷 如果是在智能手机、无人驾驶等联邦学习的环境下，任务节点之间的数据共享将不可行，使该方法存在一定的局限性。而且，该方法假设任务节点之间的关联度是静态且相同的（体现为邻接矩阵的权重取值），而现实场景下任务节点之间的关联度是不同甚至是动态的，我们可以考虑根据工作节点参数之间的距离或工作节点梯度变化程度来动态调整。
(2) 周期性同步的去中心化优化方法
描述 Yang P等人[5]设计了一个去中心化的原始-对偶优化方法来求解在线多任务学习问题。在该方法中采用了一种周期性同步的措施（周期为\(\tau\)），这种周期化同步的方法摊销了同步操作所带来的的（等待低速节点）的时间延迟。在论文中，邻接权重矩阵\(\mathbf{S}\)固定为一个稀疏矩阵（当\(t \text{ mod } \tau =0\)时,\(\mathbf{S}_t = \mathbf{S}\)；其余情况邻接矩阵\(\mathbf{S}_t = \mathbf{I}_{m\times m}\)，意味着节点间没有同步与通信）。
优点 依靠周期性的优化算法降低了同步操作带来的（等待低速节点）的开销。
缺陷 本质上邻接矩阵的权重仍然没有根据工作节点的情况进行变化，
(3) 分布式在线多任务学习中的拜占庭容错问题
描述 Li J等人[6]设计了一个对任意数量的拜占庭攻击者具有容错性的任务节点之间的权重更新算法。在分布式在线多任务学习的环境下，任务节点之间的权重可以表示任务之间的关系，该权重可以动态地进行学习和调整。一种常见的调整方法为根据不同任务节点参数之间的距离进行调整。然而，这种调整方法受到拜占庭攻击者的影响。论文设计了一种特别的权重调整方法，该方法能够过滤掉来自邻接点中的拜占庭攻击者的信息，而只使用剩余邻接点的信息。该算法对于任意数量的拜占庭攻击者都适用。
优点 首先，该论文基于在线学习方法学习任务之间的关系（邻接矩阵权重可调整），具有一定的优越性。其次，论文将拜占庭容错性引入多任务学习研究，带来了一个不一样的视角;最后，每轮迭代只需要花费关于邻接点数量和任务维度的线性时间复杂度的时间开计算权重更新，具有计算高效性。
缺陷 每轮迭代邻接矩阵的权重更新需要解一个最优化问题，而该问题需要同步操作，对于低速的节点来说会到来较高的时间延迟（尤其当任务节点数量）较多时。
(4) 基于混合分布的联邦多任务学习模型
描述 Marfoq O等人[7]设计了一个基于混合数据分布的联邦(分布式)多任务模型。该模型假设每个任务节点的数据是不能移动且并不是同分布的(这也是联邦学习中经常面对的情况)。作者认为多任务学习正好可以用于解决联邦学习中这种节点数据不是同分布的情况。该篇论文假设每个论文节点是\(M\)个概率分布的混合分布(对任务\(t\)的数据集，第\(j\)个概率分布对应的权重为\(\pi_{tj}^*\))，这样的优点在于每个任务节点可以与其他任务节点共享知识。此外论文也假设每个任务节点的权重是\(M\)个权重参数的混合分布，还可以拓展到簇状多任务学习的情况（簇状多任务学习的一种情况[19]就是强调每个任务的参数分布是多个任务簇分布的混合分布,每个任务簇共享一个模型。应用在这里如果任务\(t\)在簇\(c\)中，则\(\pi_{tc}^* = 0\)）。最后，作者给出了该算法的中心化和去中心化实现形式。其中去中心化实现中，任务节点将会和其邻接节点交换权重。
优点 以多任务学习之矛攻联邦学习之盾，针对联邦学习数据分布不一致问题给出了较好的解决方案。
缺陷 联邦学习的情境下增加了数据不能转移的限制，一定程度上也导致了多任务可能无法收敛到全局最优。而且每轮迭代每个任务都需要同步参数交互操作，如果存在通信带宽较小的节点将会导致较大的时延。此外，通过任务参数的混合分布，较好地和簇状多任务学习练习起来。
2. 个人看法
根据目前我所阅读的论文情况，⽬前的针对多任务学习并行化的论文大多关注于形如\(F(\bm{\theta})=f(\bm{\theta})+g(\bm{\theta})\)的基于正则化的多任务学习，因为这样可以使并行化的方法更有通用性。目前我也准备集中解决这类问题的并行性。
我们回顾上面提到的所有方法的优缺点，在中心化模型方面，Baytas I M等人[1]提出的基于近端映射的同步和异步算法和Zhang Y[13]提出的基于分解代理损失函数的并行化方法，都着重于针对正则化多任务学习的提供一个通用的并行架构，但[1]会带来较高的通信量，[13]的并行化程度非常有限。Wang J等人[14]提出的基于去偏lasso的分布式方法尽管大大减少了通信量，但只适用于增强group sparse的正则项（如group lasso等），不能进一步推广到其他的基于正则化的方法（比如基于任务簇/层次化的多任务学习）。可以说，在中心化模型方面，目前以上的工作都尚未对基于任务簇/层次化的多任务学习⽅法提供一个加速比高的并⾏化手段。
此外，在去中心化模型方面，不同的论文在去中心化的基础上由不同的角度做了许多工作。Zhang C等人[4]打破了任务间的数据壁垒，为了避免陷入多任务的帕累托最优情形，使每个任务之间可以共享数据，且每个任务节点将有机会负责所有任务。这种方法有悖于数据隐私保护的观念，在如今联邦学习的大环境下显得并不可行。Yang P等人[5]方法创新点一是其使用的原始-对偶优化方法，而是其提出的周期性优化的思想，这种思想大大减小了去中心化环境中任务节点与相邻节点间的通信等待时延。Li J[6]等人认为邻接矩阵权重更新过程中的任务之间的参数相似度计算对拜占庭攻击缺少容错性，设计了一个拜占庭容错的邻接矩阵权重更新算法，这个从分布式系统/联邦学习出发的视角对我很有启发。 Marfoq O等人[7]从联邦学习出发，因各节点的数据分布不同将多任务学习引入到联邦学习情景中，体现了学科之间的交融性；同时也假设了各节点的权重服从混合分布，很好地和簇状多任务学习联系起来。
目前我最感兴趣的是和任务簇多任务学习结合的[7]联邦学习算法。后面的科研也会在这篇论文的基础上进行改进，这里就不展开详细叙述了。
参考文献
- [1] Baytas I M, Yan M, Jain A K, et al. Asynchronous multi-task learning[C]//2016 IEEE 16th International Conference on Data Mining (ICDM). IEEE, 2016: 11-20.
- [2] Liu S, Pan S J, Ho Q. Distributed multi-task relationship learning[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017: 937-946.
- [3] Dinuzzo F, Pillonetto G, De Nicolao G. Client–server multitask learning from distributed datasets[J]. IEEE Transactions on Neural Networks, 2010, 22(2): 290-303.
- [4] Zhang C, Zhao P, Hao S, et al. Distributed multi-task classification: A decentralized online learning approach[J]. Machine Learning, 2018, 107(4): 727-747.
- [5] Yang P, Li P. Distributed primal-dual optimization for online multi-task learning[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2020, 34(04): 6631-6638.
- [6] Li J, Abbas W, Koutsoukos X. Byzantine Resilient Distributed Multi-Task Learning[J]. arXiv preprint arXiv:2010.13032, 2020.
- [7] Marfoq O, Neglia G, Bellet A, et al. Federated multi-task learning under a mixture of distributions[J]. Advances in Neural Information Processing Systems, 2021, 34.
- [8] Ji S, Ye J. An accelerated gradient method for trace norm minimization[C]//Proceedings of the 26th annual international conference on machine learning. 2009: 457-464.
- [9] P. L. Combettes and V. R. Wajs, “Signal recovery by proximal forwardbackward splitting,” Multiscale Modeling & Simulation, vol. 4, no. 4, pp. 1168–1200, 2005.
- [10] Z. Peng, T. Wu, Y. Xu, M. Yan, and W. Yin, “Coordinate-friendly structures, algorithms and applications,” Annals of Mathematical Sciences and Applications, vol. 1, pp. 57–119, 2016.
- [11] Z. Peng, Y. Xu, M. Yan, and W. Yin, “ARock: An algorithmic framework for asynchronous parallel coordinate updates,” SIAM Journal on Scientific Computing, vol. 38, no. 5, pp. A2851–A2879, 2016.
- [12] A. Beck and M. Teboulle, “A fast iterative shrinkagethresholding algorithm for linear inverse problems,” SIAM Journal on Imaging Sciences, 2009
- [13] Zhang Y. Parallel multi-task learning[C]//2015 IEEE International Conference on Data Mining. IEEE, 2015: 629-638.
- [14] Wang J, Kolar M, Srerbo N. Distributed multi-task learning[C]//Artificial intelligence and statistics. PMLR, 2016: 751-760.
- [15] Smith V, Chiang C K, Sanjabi M, et al. Federated multi-task learning[J]. Advances in Neural Information Processing Systems, 2017.