并行多任务学习论文阅读（五）：论文阅读总结

做为最后一篇并行多任务学习的论文阅读记录，我决定对我目前为止粗读和精读的论文进行一次总结，然后陈述一些个人对该研究领域的见解和想法。

论文总结归纳

目前已经有许多论文对多任务学习提出了并行化策略，我们可以大致概括如下几类：

(1) 基于近端梯度的同步算法

描述 多任务学习优化中首先面临的问题即目标函数\(F(\bm{\theta}) = f(\bm{\theta}) + g(\bm{\theta})\)中正则项\(g(\bm{\theta})\)的非凸性，而在数值优化里面近端梯度算法（包括一阶的FISTA、SpaRSA和最近提出的二阶的PNOPT）可以有效求解这种所谓的复合凸目标函数。而近端梯度算法一般分为\(f(\bm{\theta})\)的梯度计算和近端映射两个步骤。\(f(\bm{\theta})\)的梯度计算可以很容易地分摊到各个任务节点上（每个任务节点负责计算一个任务对应的梯度）；然后待所有任务节点运算完毕后，将梯度传往主节点后汇集，并在此基础上对权重矩阵进行近端映射，以得到更新后的参数矩阵。最后，主节点又将更新了的参数向量分发给各任务节点，开始下一轮迭代。

优点 算法逻辑简单清晰且通用性强，几乎可以推广到所有基于正则化的多任务学习。

缺陷 因为是基于同步通信的优化算法，如果有节点传输带宽过低（或直接down）掉，就会拖累整个系统的运行，导致不能容忍的运行时间和运算资源的浪费。

(2) 基于近端梯度的异步算法

描述 中心节点只要收到了来自一个任务节点的已经算好的梯度，就会马上对模型的参数矩阵进行更新，而不用等待其他任务节点完成计算。特别地，在论文中采用了一种(基于近端梯度的)前向-后向算子分裂方法来求解目标函数，且最终的迭代方法采用论文中讨论的KM迭代(KM迭代能够很好地适用于我们这里的异步环境)。

优点 因为通信是异步的，可以提高系统的吞吐率。

缺陷 如果对内存的读取不加锁的话会导致不一致性（inconsistency）问题，可能降低算法整体的收敛速率。

(2) 基于分解代理损失函数的算法

描述 对于形如\(F(\bm{\theta}) = f(\bm{\theta}) + g(\bm{\theta})\)的符合目标函数，FISTA算法采取的策略是构建代理损失函数\(Q_{\mathcal{L}}(\bm{\theta}, \hat{\bm{\theta}})\)，然后对该代理损失函数的求解进行并行化。在论文《Parallel Multi-Task Learning》中则更进一步，首先将原始的\(F(\bm{\theta}) = f(\bm{\theta}) + g(\bm{\theta})\)问题先转换为了对偶问题，然后用FISTA算法对对偶问题进行迭代求解（在求解的过程中我们可以构建代理损失函数，然后对代理损失函数进行并行化）。

优点 代理损失函数易于分解，且该方法通用性强

缺陷 如果代理损失函数构建不恰当，则可能导致其做为原损失函数的上界过松，降低优化效果。

(3) 基于本地去偏估计的算法

描述 基于近端梯度的优化算法会带来较大的通信开销，但如果完全不通信就会退化为单任务学习。为了解决这个难点，论文《distributed multitask learning》提出了基于去偏lasso模型。该算法介于两者之间，只需要一轮通信，但仍然保证了使用group regularization所带来的统计学效益。

优点 减少了通信次数而不影响多任务学习的正常进行。

缺点 局限于基于基于group sparse正则项的多任务学习，难以进一步推广。

个人看法

根据目前我所阅读的论文情况，⽬前关于不同的损失函数和不同的正则项已经有很多学者做过了，不过⽬前基于任务簇/层次化的多任务学习⽅法还没有⼈对专门其并⾏化。
聚类⽅法将不同任务分为不同的独⽴簇，每个簇存在于⼀个低维空间，每个簇的任务共⽤同⼀个模型，最终通过交替迭代学习不同簇的分配权重和每个簇的模型权重。聚类任务的特性决定着任务之间有很强的关联性，这⽅⾯并⾏的难度预计比其他类别大，可能也是这方面文章较少的原因。
目前我打算分以下几步来入手该方向：

• 所有任务簇方法中，论文中所采取的方法最为简单，可以先以此做为为突破口进行并行，然后逐步扩展到其他簇状多任务学习类别中。
• 对论文中提到的模型在Spark上采用单节点做为baseline进行实现，后续参照此串行进行对比。
• 在Spark集群上采用多节点实现论文中提到的基于近端梯度的同步/异步算法（用于求解我们这里的簇状多任务问题），并计算加速比和收敛率，方便后续参照进行对比。
• 尝试算法中的构造代理损失函数法改造并应用与我们这里的簇状多任务学习问题，并与传统的同步/异步算法相比较。
• 尝试论文中提到的方法，看对簇状聚类的正则项能否进行本地的去偏估计，这样应该能将其充分并⾏化而减少通信量，做为论文来说也是最有创新性的一个亮点。
• 尝试将实现好的并行算法推广到簇状多任务学习论文中所提到的模型架构，最终尝试建立一个针对簇状多任务学习统一的并行框架。

参考文献

• [1] 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.
• [2] 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.
• [3] P. L. Combettes and V. R. Wajs, “Signal recovery by proximal forwardbackward splitting,” Multiscale Modeling & Simulation, vol. 4, no. 4, pp. 1168–1200, 2005.
• [4] 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.
• [5] 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.
• [6] A. Beck and M. Teboulle, “A fast iterative shrinkagethresholding algorithm for linear inverse problems,” SIAM Journal on Imaging Sciences, 2009
• [7] Zhang Y. Parallel multi-task learning[C]//2015 IEEE International Conference on Data Mining. IEEE, 2015: 629-638.
• [8] Wang J, Kolar M, Srerbo N. Distributed multi-task learning[C]//Artificial intelligence and statistics. PMLR, 2016: 751-760.
• [9] Kumar A, Daume III H. Learning task grouping and overlap in multi-task learning[J]. arXiv preprint arXiv:1206.6417, 2012.
• [10] Barzilai A, Crammer K. Convex multi-task learning by clustering[C]//Artificial Intelligence and Statistics. PMLR, 2015: 65-73.
• [11] Thrun S, O'Sullivan J. Discovering structure in multiple learning tasks: The TC algorithm[C]//ICML. 1996, 96: 489-497.
• [12] Bakker B J, Heskes T M. Task clustering and gating for bayesian multitask learning[J]. 2003.
• [13] Xue Y, Liao X, Carin L, et al. Multi-task learning for classification with dirichlet process priors[J]. Journal of Machine Learning Research, 2007, 8(1).
• [14] Zhou J, Chen J, Ye J. Clustered multi-task learning via alternating structure optimization[J]. Advances in neural information processing systems, 2011, 2011: 702.
• [15] Kang Z, Grauman K, Sha F. Learning with whom to share in multi-task feature learning[C]//ICML. 2011.
• [16] Han L, Zhang Y. Learning multi-level task groups in multi-task learning[C]//Twenty-Ninth AAAI Conference on Artificial Intelligence. 2015.