How to go beyond the quadratic cost in optimization? Through Bregman divergences? Can we go beyond and non-Euclidean? I will show that by replacing the quadratic or Bregman regularizer with a general cost function c(x,y) and using a majorize-minimize framework we obtain a generic class of algorithms encompassing mirror/natural/Riemannian gradient descent by reframing them as an alternating minimization, each for a different cost c(x,y). We prove that a five-point property inspired from [Csiszár and Tusnady 1984] provides (sub)linear rates, extending the known theory of (relative) smoothness and convexity, and incorportating them into c-concavity and cross-convexity. Both notions are connected with the theory of cross-curvature in optimal transport and give a new spin to studying global convergence rates, e.g. for Newton method, in a systematic manner.
This is a joint work with Flavien Léger (INRIA Paris) https://arxiv.org/abs/2305.04917