Efficient Bregman Projections onto the Permutahedron and Related Polytopes
Efficient Bregman Projections onto the Permutahedron and Related Polytopes
复制标题
全面体和相关多面体的高效布雷格曼投影
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Stephen J. Wright
中科院分区：
文献类型：
--
作者：
Cong Han Lim;Stephen J. Wright
证明了在一致可分的Bregman散度下投影到置换面体PH(C)上的问题可归结为保序优化问题。这使得我们可以利用已知的快速算法来改进最近关于Bregman投影到置换面体的几个结果。此外，我们还提出了一种新的算法MergeAndPool，当向量c中不同的表项d很小时，该算法具有更好的复杂性，单纯形就是这样一个例子，其中c=(1，0，0，.。。，0)和d=2。对于某些流行的Bregman散度，MergeAndPool运行在O(Nlogd)内，并且需要O((Nlogd)logU)来寻找一般的一致可分Bregman发散的闭合解，其中U是包含对偶解分量的区间的宽度上的界。这些估计匹配或改进了所有Bregman投影问题在各种置换面体上的已知界，包括投影到单纯形上的最新结果。同样的复杂性界限也适用于带符号的置换面体，这是一种将`1-ball作为特例包括在内的类。总之，这项工作描述了一种快速统一的方法来解决这类众所周知的问题。
The problem of projecting onto the permutahedron PH(c)—the convex hull of all permutations of a fixed vector c—under a uniformly separable Bregman divergence is shown to be reducible to the Isotonic Optimization problem. This allows us to employ known fast algorithms to improve on several recent results on Bregman projections onto permutahedra. In addition, we present a new algorithm MergeAndPool that have better complexity when the number of distinct entries d in the vector c is small, the simplex being one such example, with c = (1, 0, 0, . . . , 0) and d = 2. MergeAndPool runs in O(n log d) for certain popular Bregman divergence measures and requires O((n log d) log U ) to find -close solutions for general uniformly separable Bregman divergences, where U is a bound on the width of the interval containing the dual solution components. These estimates matches or improves best known bounds for all Bregman projection problems onto various permutahedra, including recent results for projection onto the simplex. The same complexity bounds apply to signed permutahedra, a class that includes the `1-ball as a special case. In summary, this work describes a fast unified approach to this wellknown class of problems.