# Gradient descent with a general cost

arXiv: https://arxiv.org/abs/2305.04917 · HTML: https://mlsanity.com/paper/2305.04917/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2023.

## Built on by (most cited first, 4 of 4)

- [Mirror and Preconditioned Gradient Descent in Wasserstein Space](https://mlsanity.com/paper/2406.08938/) (2024)
- [A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm](https://mlsanity.com/paper/2412.09235/) (2024)
- [Primal-dual algorithm for contextual stochastic combinatorial optimization](https://mlsanity.com/paper/2505.04757/) (2025)
- [Hessian stability and convergence rates for entropic and Sinkhorn potentials via semiconcavity](https://mlsanity.com/paper/2504.11133/) (2025)

## Abstract (arXiv)

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.