convergence rates – Optimization Online

Fast convergence of inertial primal-dual dynamics and algorithms for a bilinearly coupled saddle point problem

Published: 2023/09/19

Convex Optimization convergence rates, Damped inertial dynamics, Iterates convergence, nesterov's accelerated gradient method, numerical algorithm, saddle point problem

This paper is devoted to study the convergence rates of a second-order dynamical system and its corresponding discretization associated with a continuously differentiable bilinearly coupled convex-concave saddle point problem. First, we consider the second-order dynamical system with asymptotically vanishing damping term and show the existence and uniqueness of the trajectories as global twice continuously differentiable … Read more

Provably Faster Gradient Descent via Long Steps

Published: 2023/07/11, Updated: 2023/07/20

Benjamin Grimmer

Convex Optimization, Semi-definite Programming acceleration, computer-assisted, convergence rates, convex, gradient descent, PEP, smooth

This work establishes provably faster convergence rates for gradient descent in smooth convex optimization via a computer-assisted analysis technique. Our theory allows nonconstant stepsize policies with frequent long steps potentially violating descent by analyzing the overall effect of many iterations at once rather than the typical one-iteration inductions used in most first-order method analyses. We … Read more

Affine invariant convergence rates of the conditional gradient method

Published: 2021/12/29

Javier F. Peña

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