Efficient First Order Methods for Linear Composite Regularizers
Efficient First Order Methods for Linear Composite Regularizers
复制标题
DOI：
--
复制
发表时间：
2011-04
期刊：
影响因子：
--
通讯作者：
Andreas Argyriou;C. Micchelli;M. Pontil;Lixin Shen;Yuesheng Xu
中科院分区：
文献类型：
--
作者：
Andreas Argyriou;C. Micchelli;M. Pontil;Lixin Shen;Yuesheng Xu
机器学习和统计学中的一类正则化问题使用正则化项，该正则化项通过将简单的凸函数\omega与线性变换组合而获得。此设置包括Group Lasso方法、Fused Lasso和其他全变差方法、多任务学习方法等等。在本文中，我们提出了一个通用的方法来计算这类正则化的邻近算子，假设函数\omega的邻近算子是已知的。我们的方法建立在最佳一阶优化方法的最新研究路线，并使用不动点迭代数值计算的邻近算子。它比当前的方法更通用，并且正如我们通过数值模拟所表明的那样，在计算上比无法实现最佳速率的可用一阶方法更有效。特别是，我们的方法优于最先进的O（1/T）方法重叠组Lasso和匹配最佳O（1/T^2）方法融合Lasso和树结构组Lasso。
A wide class of regularization problems in machine learning and statistics employ a regularization term which is obtained by composing a simple convex function \omega with a linear transformation. This setting includes Group Lasso methods, the Fused Lasso and other total variation methods, multi-task learning methods and many more. In this paper, we present a general approach for computing the proximity operator of this class of regularizers, under the assumption that the proximity operator of the function \omega is known in advance. Our approach builds on a recent line of research on optimal first order optimization methods and uses fixed point iterations for numerically computing the proximity operator. It is more general than current approaches and, as we show with numerical simulations, computationally more efficient than available first order methods which do not achieve the optimal rate. In particular, our method outperforms state of the art O(1/T) methods for overlapping Group Lasso and matches optimal O(1/T^2) methods for the Fused Lasso and tree structured Group Lasso.