Research map / Optimization / Optimizers
On the Convergence of Projected Bures-Wasserstein Gradient Descent under Euclidean Strong Convexity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves global linear convergence of projected Bures-Wasserstein gradient descent for Euclidean strongly convex, smooth objectives over Euclidean-convex constraint sets, and derives a closed-form BW-ball projection.
Problem
Convergence of Bures-Wasserstein gradient descent for constrained optimization over positive-definite matrices, where existing analyses assume geodesic convexity or cover only unconstrained problems.
Approach
Relates Euclidean PL inequality and smoothness to their BW-geometric analogs, yielding linear convergence under Euclidean strong convexity without geodesic convexity; and gives a closed-form projection onto BW distance balls, making projected BWGD cheap.
Key results
- Proves linear convergence of projected BWGD under Euclidean strong convexity and smoothness with a rate depending on the eigenvalue ratio kappa and the PL coefficient (Theorem 4.10).
- Derives a closed-form projection onto the BW ball (Proposition 4.1), avoiding the n-dimensional SDP needed for direct projection.
- In experiments, projected BWGD with vanilla step size converges much faster than Frank-Wolfe on WDRO-MMSE and constrained barycenter problems; Euclidean GD with projection fails to converge to the global minimum.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use projected BWGD with the vanilla step size instead of Frank-Wolfe | Projected BWGD · WDRO-MMSE | surrogate duality gap | Helped |
| use projected BWGD with Armijo search instead of FAFW | Projected BWGD · WDRO-MMSE | surrogate duality gap | No clear effect |
| use projected BWGD with Armijo search instead of FAFW | Projected BWGD · Constrained barycenter | surrogate duality gap | Helped |
| use FAFW | Constrained barycenter · Constrained barycenter | surrogate duality gap | Hurt |
| use Euclidean gradient descent with BW projection instead of projected BWGD | Euclidean gradient descent with BW projection · WDRO-MMSE and constrained barycenter experiments | surrogate duality gap | Hurt |
Surprising findings
- Euclidean gradient descent with BW-ball projection fails to converge to the global minimum despite strong convexity in the Euclidean sense.
- Lower bound example shows the convergence rate of BWGD must depend on lambda_min even when iterates are well-conditioned.
Limitations
- Linear rate depends on assumed bounded eigenvalues of iterates (Assumption 4.5) and the PL constant has worse dependence on problem parameters in the constrained case.
- Analysis is for Euclidean strong convexity and smoothness; weaker assumptions and stochastic variants are left open.
- Armijo-step variant lacks theoretical convergence proof.
Experimental setup
Benchmarks: WDRO-MMSE synthetic problem (n=200) constrained Gaussian barycenter synthetic problem (n=30, N=50)
Metrics: surrogate duality gap convergence speed vs iterations/time
Baselines: Frank-Wolfe fully adaptive Frank-Wolfe Euclidean gradient descent with projection Armijo BWGD
Builds on: Chewi et al. 2020 BW barycenter analysis Altschuler et al. 2021 BW barycenter convergence Boumal et al. 2019 geodesic non-convex Riemannian convergence Frank-Wolfe for BW ball constraints (Taskesen et al. 2023)
Closest papers by meaning
- Mirror and Preconditioned Gradient Descent in Wasserstein Space (NeurIPS 2024 · similarity 0.87)
- Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees (ICML 2025 · similarity 0.86)
- Stochastic variance-reduced Gaussian variational inference on the Bures-Wasserstein manifold (ICLR 2025 · similarity 0.86)
- A Study of First-Order Methods with a Deterministic Relative-Error Gradient Oracle (ICML 2024 · similarity 0.86)
- Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization (ICML 2025 · similarity 0.86)
- Hessian-guided Perturbed Wasserstein Gradient Flows for Escaping Saddle Points (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.