Timezone: »

Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent
Jason Altschuler · Sinho Chewi · Patrik R Gerber · Austin Stromme

Fri Dec 10 08:30 AM -- 10:00 AM (PST) @

We study first-order optimization algorithms for computing the barycenter of Gaussian distributions with respect to the optimal transport metric. Although the objective is geodesically non-convex, Riemannian gradient descent empirically converges rapidly, in fact faster than off-the-shelf methods such as Euclidean gradient descent and SDP solvers. This stands in stark contrast to the best-known theoretical results, which depend exponentially on the dimension. In this work, we prove new geodesic convexity results which provide stronger control of the iterates, yielding a dimension-free convergence rate. Our techniques also enable the analysis of two related notions of averaging, the entropically-regularized barycenter and the geometric median, providing the first convergence guarantees for these problems.

Author Information

Jason Altschuler (MIT)
Sinho Chewi (Massachusetts Institute of Technology)
Patrik R Gerber (Massachusetts Institute of Technology)
Austin Stromme (MIT)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors