Robust Sublinear Convergence Rates for Iterative Bregman Projections
This work provides robust convergence guarantees for iterative methods in optimization, benefiting researchers and practitioners in machine learning and computational mathematics, though it is incremental as it extends known results to more general settings.
The paper tackles the problem of approximating linear programs with split constraints via entropic regularization and cyclic KL Bregman projections, proving an O(1/k) convergence rate with a constant scaling linearly in 1/γ, which extends guarantees from entropic optimal transport to broader problems. As an application, it derives the flow-Sinkhorn algorithm for Wasserstein-1 distance on graphs, achieving ε-additive accuracy in O(p/ε^4) operations.
Entropic regularization provides a simple way to approximate linear programs whose constraints split into two (or more) tractable blocks. The resulting objectives are amenable to cyclic Kullback-Leibler (KL) Bregman projections, with the classical Sinkhorn algorithm for optimal transport (balanced, unbalanced, gradient flows, barycenters, \dots) as the canonical example. Assuming uniformly bounded primal mass and dual radius, we prove that the dual objective of these KL projections decreases at an $O(1/k)$ rate with a constant that scales only linearly in $1/γ$, where $γ$ is the entropic regularization parameter. This extends the guarantees known for entropic optimal transport to any such linearly constrained problem. Following the terminology introduced in [Chizat et al 2025], we call such rates "robust", because this mild dependence on $γ$ underpins favorable complexity bounds for approximating the unregularized problem via alternating KL projections. The crucial aspect of the analysis is that the dual radius should be measured according to a block-quotient dual seminorm, which depends on the structure of the split of the constraint into blocks. As an application, we derive the flow-Sinkhorn algorithm for the Wasserstein-1 distance on graphs. It achieves $ε$-additive accuracy on the transshipment cost in $O(p/ε^{4})$ arithmetic operations, where $p$ is the number of edges.