Skip to yearly menu bar Skip to main content


Poster

A Bregman Divergence View on the Difference-of-Convex Algorithm

Oisín Faust · Hamza Fawzi · James Saunderson

Auditorium 1 Foyer 116

Abstract:

The difference of convex (DC) algorithm is a conceptually simple method for the minimization of (non)convex functions that are expressed as the difference of two convex functions. An attractive feature of the algorithm is that it maintains a global overestimator on the function and does not require a choice of step size at each iteration.By adopting a Bregman divergence point of view, we simplify and strengthen many existing non-asymptotic convergence guarantees for the DC algorithm. We further present several sufficient conditions that ensure a linear convergence rate, namely a new DC Polyak-Łojasiewicz condition, as well as a relative strong convexity assumption. Importantly, our conditions do not require smoothness of the objective function.We illustrate our results on a family of minimization problems involving the quantum relative entropy, with applications in quantum information theory.

Live content is unavailable. Log in and register to view live content