1.难点-如何实现高效的通信

我们考虑下列的多任务优化问题:

[ underset{textbf{W}}{min} sum_{t=1}^{T} [frac{1}{m_t}sum_{i=1}^{m_t}L(y_{ti}, langle bm{w}_t, bm{x}_{ti} rangle)]+lambda text{pen}(textbf{W}) tag{1} ]

这里(text{pen}(mathbf{W}))是一个用于增强group sparse的正则项(参见联合特征学习(joint feature learning),常为(l_1/l_2)(l_1/l_{infin})范数的组合,用于只保留对所有任务有用的特征)。比如。在group lasso penalty[1][2] 中使用 (text{pen}(mathbf{W}) =sum_{t=1}^T||bm{w}_t||_2 = sum_{t=1}^T (sum_{j=1}^d{w}_{jt}^2 )^{1/2})(这里(d)为特征维度,(T)为任务数,(bm{w}_t)(mathbf{W})的第(t)列); (text{iCAP})使用(text{pen}(mathbf{W}) = ||mathbf{W}||_{infin, 1} = sum_{j=1}^d||bm{w}^j||_{infin}= sum_{j=1}^dunderset{1leqslant t leqslant T}{text{max}}|w_{jt}|) [3][4](这里(bm{w}^j)是指(mathbf{W})的第(j)行。注意区分这个和矩阵的(infin)范数,求和与求最大的顺序是不一样的!这里相当于求向量的无穷范数之和),等等。
在分布式的环境中,我们可以按照文章《分布式多任务学习论文阅读(二)同步和异步优化算法》(链接:https://www.cnblogs.com/orion-orion/p/15487700.html)提到的基于近端梯度的同步/异步优化算法来优化问题((1)),但是正如我们在该篇博客中所说的,这种方法需要多轮的通信,时间开销较大。这样,如何实现机器间的有效通信是我们必须要想办法解决该问题。

现在的热点解决方案是采用去中心化(decentralize)的思想,即使任务节点绕过主节点,直接利用相邻任务节点的信息,这样可以大大降低通信量[5][6][7]。这种方法我们未来会着重介绍,此时按下不表。

当然,读者可能会思考,我们可以不可以直接每个任务各自优化各的(l_1)正则目标函数,即每个任务直接采用近端梯度法求解下列的local lasso问题:

[ hat{textbf{w}}_t = underset{textbf{w}_t}{text{argmin}}frac{1}{m_t}sum_{i=1}^{m_t}L(y_{ti}, langle textbf{w}_t, textbf{x}_{ti} rangle)+lambda_t ||textbf{w}_t||_{1} ]

很遗憾,这种方法虽然做到了不同任务优化的解耦,但本质上变成了单任务学习,没有充分利用好多任务之间的联系(任务之间的练习须依靠group sparse正则项(text{pen}(textbf{W}))来实现)。那么,有没有即能够减少通信次数,又能够保存group regularization的基本作用呢?(暂时不考虑任务节点相互通信的去中心化的方法)

2. 基于去偏lasso模型的分布式算法

论文《distributed multitask learning》[8]提出的算法介于传统的分布式近端梯度法和local lasso之间,其计算只需要一轮通信,但仍然保证了使用group regularization所带来的统计学效益。 该论文提出的算法描述如下:

去偏lasso算法

这里我们特别说明一下第4行的操作,(m_t^{-1}mathbf{X}_t^T(bm{y}_t - mathbf{X}_that{bm{w}}_t))
是损失函数的次梯度;矩阵(textbf{M}_tin mathbb{R}^{d times d})是Hessian矩阵的近似逆,(m_t)是任务(t)对应的样本个数(事实上原论文假定(m_1=m_2=...=m_T));节点(t)对应的训练数据是((mathbf{X}_t, bm{y}_t))


这种求去偏lasso估计量的方法由最近关于高维统计[9][10][11]的文章提出,这些论文都企图去除引入算法第3行所示的(l_1)正则项所导致的偏差(bias),具体方法是运用(l_1)正则损失函数关于(bm{w}_t)的次梯度来构造得到参数成分的无偏估计量(hat{bm{w}}^u_t)。下面我们会参照去偏估计器的采样分布,但我们的最终目标不同。[9][10][11]这三篇论文构造矩阵(mathbf{M})的方法不同,本篇论文主要参照论文[11]的方法,复合假设。每个机器使用矩阵(mathbf{M}_t=(hat{bm{m}}_{tj})_{j=1}^d),它的行是:

[begin{aligned} & hat{bm{m}}_{tj} = underset{bm{m}_j in mathbb{R}^p}{text{argmin}} quad bm{m}_j^That{mathbf{Sigma}_t}bm{m}_j \ & text{s.t.} quad ||hat{mathbf{Sigma}}_tbm{m}_j - bm{e}_j ||_{infin} leqslant u. end{aligned} ]

这里(bm{e}_j)是第(j)个元素为1其他元素为0的(标准基)向量,(hat{Sigma}_t={m_t}^{-1} mathbf{X}_t^Tmathbf{X}_t)


当每个任务节点得到去偏估计量(hat{bm{w}}_t^u)后,就会将其送往主节点。在主节点那边,待从所有任务节点收到({hat{bm{w}}_t^u}_{t=1}^T)后,就来到了第(12)行的操作。第(12)行的操作在master节点的操作充分利用了不同任务参数之间的共享稀疏性,即主节点将接收到的估计量拼接成矩阵(hat{textbf{W}}^u=(hat{bm{w}}_1^u, hat{bm{w}}_2^u,..., hat{bm{w}}_T^u)),然后再执行hard thresholding以过得(mathbf{S})的估计量:

[hat{S}(Lambda)={j text{ }| text{ } ||hat{textbf{W}}_j^u||_2 > Lambda } ]

参考文献

  • [1] Yuan M, Lin Y. Model selection and estimation in regression with grouped variables[J]. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2006, 68(1): 49-67.
  • [2] Friedman J, Hastie T, Tibshirani R. A note on the group lasso and a sparse group lasso[J]. arXiv preprint arXiv:1001.0736, 2010.
  • [3] Zhao P, Rocha G, Yu B. The composite absolute penalties family for grouped and hierarchical variable selection[J]. The Annals of Statistics, 2009, 37(6A): 3468-3497.
  • [4] Liu H, Palatucci M, Zhang J. Blockwise coordinate descent procedures for the multi-task lasso, with applications to neural semantic basis discovery[C]//Proceedings of the 26th Annual International Conference on Machine Learning. 2009: 649-656.
  • [5] 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.
  • [6] 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.
  • [7] Li J, Abbas W, Koutsoukos X. Byzantine Resilient Distributed Multi-Task Learning[J]. arXiv preprint arXiv:2010.13032, 2020.
  • [8] Wang J, Kolar M, Srerbo N. Distributed multi-task learning[C]//Artificial intelligence and statistics. PMLR, 2016: 751-760.
  • [9] Zhang C H, Zhang S S. Confidence intervals for low dimensional parameters in high dimensional linear models[J]. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2014, 76(1): 217-242.
  • [10] Van de Geer S, Bühlmann P, Ritov Y, et al. On asymptotically optimal confidence regions and tests for high-dimensional models[J]. The Annals of Statistics, 2014, 42(3): 1166-1202.
  • [11] Javanmard A, Montanari A. Confidence intervals and hypothesis testing for high-dimensional regression[J]. The Journal of Machine Learning Research, 2014, 15(1): 2869-2909.
  • [12] 杨强等. 迁移学习[M].机械工业出版社, 2020.
内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/orion-orion/p/15535613.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!