Efficient displacement convex optimization with particle gradient descent
This provides theoretical guarantees for a widely used method in probability measure optimization, which is incremental as it builds on existing particle gradient descent techniques.
The paper tackles the problem of optimizing displacement convex functions using particle gradient descent, establishing that O(1/ε²) particles and O(d/ε⁴) computations suffice to find ε-optimal solutions for Lipschitz functions, with improved bounds for smooth cases.
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 \emph{displacement convex} in measures. Concretely, for Lipschitz displacement convex functions defined on probability over $\mathbb{R}^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.