论文标题
在分布式网络上精确的稀疏线性回归
On Distributed Exact Sparse Linear Regression over Networks
论文作者
论文摘要
在这项工作中，我们提出了一种以分布式方式在网络上解决精确稀疏线性回归问题的算法。特别是，我们考虑了数据存储在不同计算机或试图找到具有指定稀疏k的常见回归变量的不同计算机或代理之间的问题，即L0-NORM小于或等于K。与现有的文献相反，使用L1正则化来近似稀疏度，我们用精确的稀疏性k解决了问题。我们提案中的主要新颖性在于显示出零二元性差距的问题提出，我们采用双重方法以分散的方式解决该问题。这为研究分布式优化的基础方法设定了具有明确的稀疏性约束。我们从理论和经验上表明，在适当的假设下，在每个代理解决较小和局部整数编程问题的情况下，所有代理最终都将在同一稀疏最佳回归器上达成共识。
In this work, we propose an algorithm for solving exact sparse linear regression problems over a network in a distributed manner. Particularly, we consider the problem where data is stored among different computers or agents that seek to collaboratively find a common regressor with a specified sparsity k, i.e., the L0-norm is less than or equal to k. Contrary to existing literature that uses L1 regularization to approximate sparseness, we solve the problem with exact sparsity k. The main novelty in our proposal lies in showing a problem formulation with zero duality gap for which we adopt a dual approach to solve the problem in a decentralized way. This sets a foundational approach for the study of distributed optimization with explicit sparsity constraints. We show theoretically and empirically that, under appropriate assumptions, where each agent solves smaller and local integer programming problems, all agents will eventually reach a consensus on the same sparse optimal regressor.
