Robust Sublinear Convergence Rates for Iterative Bregman Projections

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 Sinkhorn-type algorithms for optimal transport, matrix scaling, and barycenters as canonical examples. This paper gives a general blueprint for proving O(1/k) dual convergence rate with a constant that scales only linearly in 1/γ, where γ is the entropic regularization parameter. We call such rates "robust", because this mild dependence on γ underpins favorable complexity bounds for approximating the unregularized problem via alternating KL projections. The blueprint reduces the proof to a uniform primal bound and a dual bound for a quotient norm induced by the constraint split. To make these inputs usable, we propose two helper results, which rely on the non-expansiveness of the dual iterations in this quotient dual norm. Instantiating this blueprint for graph-structured transport yields a new flow-Sinkhorn algorithm for the Wasserstein-1 distance on graphs. It achieves varepsilon-additive accuracy on the transshipment cost in O(p,diameter3/varepsilon4) arithmetic operations (up to logarithmic factors), where p is the number of edges. We also provide a machine-checked Lean formalization of the core blueprint and its graph-W1 instantiation.