论文标题
稀疏性探索分布式投影到单纯子
Sparsity-Exploiting Distributed Projections onto a Simplex
论文作者
论文摘要
将矢量投射到单纯化是一个充分研究的问题，它在广泛的优化问题中出现。已经提出了许多用于确定投影的算法。但是，文献的主要重点是串行算法。我们提出了一种平行方法，该方法将输入向量分解并在多个处理器上分配以进行本地投影。当产生的投影高度稀疏时，我们的方法特别有效。例如，在I.I.D.的大规模问题中就是这种情况。条目。此外，该方法可以适应于文献中的广泛的串行算法并行。我们填补了串行算法分析中的理论空白，并为我们的平行类似物产生了相似的结果。在现实世界和模拟的各种大规模实例上进行的数值实验证明了该方法的实际有效性。
Projecting a vector onto a simplex is a well-studied problem that arises in a wide range of optimization problems. Numerous algorithms have been proposed for determining the projection; however, the primary focus of the literature has been on serial algorithms. We present a parallel method that decomposes the input vector and distributes it across multiple processors for local projection. Our method is especially effective when the resulting projection is highly sparse; which is the case, for instance, in large-scale problems with i.i.d. entries. Moreover, the method can be adapted to parallelize a broad range of serial algorithms from the literature. We fill in theoretical gaps in serial algorithm analysis, and develop similar results for our parallel analogues. Numerical experiments conducted on a wide range of large-scale instances, both real-world and simulated, demonstrate the practical effectiveness of the method.
