Efficient Bregman Projections onto the Permutahedron and Related Polytopes

Cong Han Lim, Stephen J. WrightAISTATS 2016

Abstract

Projecting vectors onto complex polytopes like the permutahedron is a fundamental challenge in machine learning, often hindered by exponential constraints. This paper introduces a unified framework that reduces Bregman projections to isotonic optimization. We present MergeAndPool, a divide-and-conquer algorithm achieving $O(n \log d)$ complexity, where $d$ is the number of distinct entries in the target vector. This approach significantly improves upon existing $O(n \log n)$ or $O(n^2)$ methods for various divergences.

Introduction

In tasks such as online ranking, sparse optimization, and probability estimation, it is frequently necessary to project a vector onto a specific geometric shape, such as the permutahedron $PH(c)$—the convex hull of all permutations of a fixed vector $c$. Standard projection methods are often prohibitively slow because a permutahedron possesses $n!$ vertices and an exponential number of linear constraints. Furthermore, many applications require Bregman divergences (e.g., KL-divergence) rather than simple Euclidean distance.

The authors address this by seeking a fast, generalized algorithm whose complexity scales with the inherent "simplicity" of the target shape, defined by the number of unique values $d$ in the vector $c$.

Methodology: Reduction and MergeAndPool

The core of the proposed approach is a three-step reduction:

  1. Reduction to Isotonic Optimization: The authors prove an "Ordering Lemma": for any uniformly separable Bregman divergence, the optimal projection preserves the sorted order of the input vector. This transforms the complex polytope constraints into a simple linear chain ($y_1 \le y_2 \le \dots \le y_n$), effectively turning the projection into an isotonic regression problem.
  2. The MergeAndPool Algorithm: Instead of the linear processing used in the classic Pool Adjacent Violators (PAV) algorithm, MergeAndPool employs a divide-and-conquer strategy. It merges intervals in a bottom-up fashion, which is more efficient for large-scale problems.
  3. Exploiting Redundancy: By identifying that the hardness of the projection depends on the number of distinct values $d$ in the base vector $c$, the algorithm uses a partial sorting strategy (e.g., "median of medians") to initialize. This ensures that for shapes like the probability simplex (where $d=2$), the complexity remains near-linear.
The MergeAndPool algorithm uses a divide-and-conquer approach to merge isotonic intervals.

Key Results and Complexity Analysis

The theoretical analysis demonstrates that MergeAndPool provides a state-of-the-art unified framework for various divergences. For "incremental" divergences like Euclidean distance and KL-divergence, the algorithm achieves a complexity of $O(n \log d)$. For more general uniformly separable Bregman divergences, the complexity is $O((n \log d) \log(U/\epsilon))$, where $U$ is the dual solution width and $\epsilon$ is the target precision.

Comparison of computational complexities for various projection types and algorithms.

As shown in the table above, the proposed method matches or exceeds the performance of specialized algorithms for the simplex while providing a much broader generalization to the permutahedron and signed permutahedra (such as the $\ell_1$-ball).

Conclusion and Limitations

While the framework is highly efficient, it is restricted to "uniformly separable" Bregman divergences. Additionally, for general divergences lacking a closed-form pooling solution, the complexity remains dependent on the desired precision $\epsilon$. Despite these constraints, the significant speedup in projection steps offers a major performance boost for online learning algorithms like Follow-The-Regularized-Leader (FTRL).

Summary updated

BibTeX
@inproceedings{lim2016efficient,
  author = {Cong Han Lim and Stephen J. Wright},
  title = {{Efficient Bregman Projections onto the Permutahedron and Related Polytopes}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
}
Figure