convergence rates – Optimization Online

Affine invariant convergence rates of the conditional gradient method

Published: 2021/12/29

Convex Optimization affine invariance, conditional gradient, convergence rates, growth condition

We show that the conditional gradient method for the convex composite problem \[\min_x\{f(x) + \Psi(x)\}\] generates primal and dual iterates with a duality gap converging to zero provided a suitable growth property holds and the algorithm makes a judicious choice of stepsizes. The rate of convergence of the duality gap to zero ranges from sublinear … Read more

A Stochastic Bregman Primal-Dual Splitting Algorithm for Composite Optimization

Published: 2021/12/22

Antonio Silveti-Falls

Cesare Molinari

Jalal Fadili

Convex and Nonsmooth Optimization, Infinite Dimensional Optimization, Stochastic Programming Banach space, bregman divergence, convergence rates, first order algorithms, noneuclidean splitting, primal-dual splitting, relative smoothness, saddle point problems, total convexity

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 … Read more