# A Stochastic Bregman Primal-Dual Splitting Algorithm for Composite Optimization

arXiv: https://arxiv.org/abs/2112.11928 · HTML: https://mlsanity.com/paper/2112.11928/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 58 references that are in the map.
- First posted on arXiv 22 Dec 2021.

## Builds on (most cited first, 18 of 18)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning](https://mlsanity.com/paper/1704.00805/) (2017)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [A Smoothed Dual Approach for Variational Wasserstein Problems](https://mlsanity.com/paper/1503.02533/) (2015)
- [Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications](https://mlsanity.com/paper/1706.04957/) (2017)
- [Semi-dual Regularized Optimal Transport](https://mlsanity.com/paper/1811.05527/) (2018)
- [Playing with Duality: An Overview of Recent Primal-Dual Approaches for Solving Large-Scale Optimization Problems](https://mlsanity.com/paper/1406.5429/) (2014)
- ["Relative-Continuity" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent](https://mlsanity.com/paper/1710.04718/) (2017)
- [A Primal-Dual Algorithm with Line Search for General Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/1803.01401/) (2018)
- [Forward-Backward Splitting with Bregman Distances](https://mlsanity.com/paper/1505.05198/) (2015)
- [Data-driven regularization of Wasserstein barycenters with an application to multivariate density registration](https://mlsanity.com/paper/1804.08962/) (2018)
- [Generalized Stochastic Frank-Wolfe Algorithm with Stochastic "Substitute" Gradient for Structured Convex Optimization](https://mlsanity.com/paper/1807.07680/) (2018)
- [Bregman Forward-Backward Operator Splitting](https://mlsanity.com/paper/1908.03878/) (2019)
- [Inexact First-Order Primal-Dual Algorithms](https://mlsanity.com/paper/1803.10576/) (2018)
- [Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization](https://mlsanity.com/paper/1901.01287/) (2019)
- [Solving Composite Monotone Inclusions in Reflexive Banach Spaces by Constructing Best Bregman Approximations from Their Kuhn-Tucker Set](https://mlsanity.com/paper/1505.00362/) (2015)

## Built on by (most cited first, 4 of 4)

- [Differentiating Nonsmooth Solutions to Parametric Monotone Inclusion Problems](https://mlsanity.com/paper/2212.07844/) (2022)
- [Stable Phase Retrieval with Mirror Descent](https://mlsanity.com/paper/2405.10754/) (2024)
- [Provable Phase Retrieval with Mirror Descent](https://mlsanity.com/paper/2210.09248/) (2022)
- [Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Size](https://mlsanity.com/paper/2608.12009/) (2026)

## Abstract (arXiv)

We study a stochastic first order primal-dual method for solving convex-concave saddle point problems over real reflexive Banach spaces using Bregman divergences and relative smoothness assumptions, in which we allow for stochastic error in the computation of gradient terms within the algorithm. We show ergodic convergence in expectation of the Lagrangian optimality gap with a rate of O(1/k) and that every almost sure weak cluster point of the ergodic sequence is a saddle point in expectation under mild assumptions. Under slightly stricter assumptions, we show almost sure weak convergence of the pointwise iterates to a saddle point. Under a relative strong convexity assumption on the objective functions and a total convexity assumption on the entropies of the Bregman divergences, we establish almost sure strong convergence of the pointwise iterates to a saddle point. Our framework is general and does not need strong convexity of the entropies inducing the Bregman divergences in the algorithm. Numerical applications are considered including entropically regularized Wasserstein barycenter problems and regularized inverse problems on the simplex.