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:
- 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.
- The
MergeAndPoolAlgorithm: Instead of the linear processing used in the classic Pool Adjacent Violators (PAV) algorithm,MergeAndPoolemploys a divide-and-conquer strategy. It merges intervals in a bottom-up fashion, which is more efficient for large-scale problems. - 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.
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.
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