Parallelization of Projection onto a Simplex

Yongzheng Dai, Chen Chen

Published 2022-04-18Version 1

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, all but one of these algorithms are serial. We address this gap by developing an efficient scheme to decompose and distribute the problem across processors, with application to a broad range of serial approaches. Our method becomes especially effective when the projection is highly sparse; which is the case, for instance, in large-scale problems with i.i.d. entries. We also fill in theoretical gaps in serial algorithm analysis; moreover we develop and analyze a variety of parallel analogues using our scheme. Numerical experiments conducted on a wide range of large-scale instances further demonstrate the effectiveness of our parallel algorithms. As our scheme can be implemented in a distributed manner, even greater practical speedups are anticipated for more specialized hardware with high levels of parallelism.