Optimization Online


A Stochastic Bregman Primal-Dual Splitting Algorithm for Composite Optimization

Antonio Silveti-Falls(tonys.falls***at***gmail.com)
Cesare Molinari(cecio.molinari***at***gmail.com)
Jalal Fadili(jalal.fadili***at***ensicaen.fr)

Abstract: 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.

Keywords: Bregman divergence; primal-dual splitting; noneuclidean splitting; saddle point problems; first order algorithms; convergence rates; relative smoothness; total convexity; Banach space.

Category 1: Convex and Nonsmooth Optimization

Category 2: Infinite Dimensional Optimization

Category 3: Stochastic Programming


Download: [PDF]

Entry Submitted: 12/22/2021
Entry Accepted: 12/22/2021
Entry Last Modified: 12/22/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society