# Efficient displacement convex optimization with particle gradient descent

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 57 references that are in the map.
- First posted on arXiv 9 Feb 2023.

## Builds on (most cited first, 22 of 22)

- [Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm](https://mlsanity.com/paper/1608.04471/) (2016)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [The Role of Permutation Invariance in Linear Mode Connectivity of Neural Networks](https://mlsanity.com/paper/2110.06296/) (2021)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [First-order Methods for Geodesically Convex Optimization](https://mlsanity.com/paper/1602.06053/) (2016)
- [Gradient Descent Can Take Exponential Time to Escape Saddle Points](https://mlsanity.com/paper/1705.10412/) (2017)
- [A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1702.05575/) (2017)
- [Escaping Saddles with Stochastic Gradients](https://mlsanity.com/paper/1803.05999/) (2018)
- [A Non-Asymptotic Analysis for Stein Variational Gradient Descent](https://mlsanity.com/paper/2006.09797/) (2020)
- [Kernel Stein Discrepancy Descent](https://mlsanity.com/paper/2105.09994/) (2021)
- [Stochastic Particle Gradient Descent for Infinite Ensembles](https://mlsanity.com/paper/1712.05438/) (2017)
- [Sparse Optimization on Measures with Over-parameterized Gradient Descent](https://mlsanity.com/paper/1907.10300/) (2019)
- [Convex Geometry and Duality of Over-parameterized Neural Networks](https://mlsanity.com/paper/2002.11219/) (2020)
- [Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositions](https://mlsanity.com/paper/2202.01331/) (2022)
- [First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time](https://mlsanity.com/paper/1711.01944/) (2017)
- [Analysis of a Two-Layer Neural Network via Displacement Convexity](https://mlsanity.com/paper/1901.01375/) (2019)
- [Sampling with Mollified Interaction Energy Descent](https://mlsanity.com/paper/2210.13400/) (2022)
- [Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization](https://mlsanity.com/paper/2012.11554/) (2020)

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

- [Posterior Sampling Based on Gradient Flows of the MMD with Negative Distance Kernel](https://mlsanity.com/paper/2310.03054/) (2023)
- [On the impact of activation and normalization in obtaining isometric embeddings at initialization](https://mlsanity.com/paper/2305.18399/) (2023)
- [Wasserstein Gradient Flows of MMD Functionals with Distance Kernel and Cauchy Problems on Quantile Functions](https://mlsanity.com/paper/2408.07498/) (2024)
- [C^*-Algebraic Machine Learning: Moving in a New Direction](https://mlsanity.com/paper/2402.02637/) (2024)
- [Data Generation without Function Estimation](https://mlsanity.com/paper/2507.08239/) (2025)

## Abstract (arXiv)

Particle gradient descent, which uses particles to represent a probability measure and performs gradient descent on particles in parallel, is widely used to optimize functions of probability measures. This paper considers particle gradient descent with a finite number of particles and establishes its theoretical guarantees to optimize functions that are displacement convex in measures. Concretely, for Lipschitz displacement convex functions defined on probability over ℝd, we prove that O(1/ε2) particles and O(d/ε4) computations are sufficient to find the ε-optimal solutions. We further provide improved complexity bounds for optimizing smooth displacement convex functions. We demonstrate the application of our results for function approximation with specific neural architectures with two-dimensional inputs.