  We present a new class of gradient-type optimization methods that extends
vanilla gradient descent, mirror descent, Riemannian gradient descent, and
natural gradient descent. Our approach involves constructing a surrogate for
the objective function in a systematic manner, based on a chosen cost function.
This surrogate is then minimized using an alternating minimization scheme.
Using optimal transport theory we establish convergence rates based on
generalized notions of smoothness and convexity. We provide local versions of
these two notions when the cost satisfies a condition known as nonnegative
cross-curvature. In particular our framework provides the first global rates
for natural gradient descent and the standard Newton's method.
