# Convergence Rates of Gradient Methods for Convex Optimization in the Space of Measures

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2021.

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

- [Convex Analysis of the Mean Field Langevin Dynamics](https://mlsanity.com/paper/2201.10469/) (2022)
- [Optimizing Functionals on the Space of Probabilities with Input Convex Neural Networks](https://mlsanity.com/paper/2106.00774/) (2021)
- [Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM](https://mlsanity.com/paper/2206.08873/) (2022)
- [A connection between Tempering and Entropic Mirror Descent](https://mlsanity.com/paper/2310.11914/) (2023)
- [Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics](https://mlsanity.com/paper/2408.07254/) (2024)
- [Smooth over-parameterized solvers for non-smooth structured optimization](https://mlsanity.com/paper/2205.01385/) (2022)
- [Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks](https://mlsanity.com/paper/2404.18769/) (2024)
- [Bregman Proximal Langevin Monte Carlo via Bregman--Moreau Envelopes](https://mlsanity.com/paper/2207.04387/) (2022)
- [Robust Feature Learning for Multi-Index Models in High Dimensions](https://mlsanity.com/paper/2410.16449/) (2024)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [A Fisher-Rao gradient flow for entropic mean-field min-max games](https://mlsanity.com/paper/2405.15834/) (2024)
- [OneAdapt: Fast Configuration Adaptation for Video Analytics Applications via Backpropagation](https://mlsanity.com/paper/2310.02422/) (2023)
- [Mirror Descent-Ascent for mean-field min-max problems](https://mlsanity.com/paper/2402.08106/) (2024)
- [A note on convergence of Wasserstein policy optimization](https://mlsanity.com/paper/2605.22622/) (2026)
- [Polynomial-time Sparse Measure Recovery: From Mean Field Theory to Algorithm Design](https://mlsanity.com/paper/2204.07879/) (2022)
- [Hard labels sampled from sparse targets mislead rotation invariant algorithms](https://mlsanity.com/paper/2603.20967/) (2026)
- [How does feature learning reshape the function space?](https://mlsanity.com/paper/2605.17718/) (2026)
- [Proximal methods for point source localisation](https://mlsanity.com/paper/2212.02991/) (2022)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [Stochastic Adaptive Gradient Descent Without Descent](https://mlsanity.com/paper/2509.14969/) (2025)

## Abstract (arXiv)

We study the convergence rate of Bregman gradient methods for convex optimization in the space of measures on a d-dimensional manifold. Under basic regularity assumptions, we show that the suboptimality gap at iteration k is in O(log(k)k--1) for multiplicative updates, while it is in O(k--q/(d+q)) for additive updates for some q ∈ 1, 2, 4 determined by the structure of the objective function. Our flexible proof strategy, based on approximation arguments, allows us to painlessly cover all Bregman Proximal Gradient Methods (PGM) and their acceleration (APGM) under various geometries such as the hyperbolic entropy and Lp divergences. We also prove the tightness of our analysis with matching lower bounds and confirm the theoretical results with numerical experiments on low dimensional problems. Note that all these optimization methods must additionally pay the computational cost of discretization, which can be exponential in d.