EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2121. Provably convergent algorithm for free-support Wasserstein barycenter of continuous non-parametric measures

Invited abstract in session TD-3: Data science meets strongly NP-Hard CO , stream Data Science Meets Optimization.

Tuesday, 14:30-16:00
Room: 1005 (building: 202)

Authors (first author is the speaker)

1. Qikun Xiang
School of Physical and Mathematical Sciences, Nanyang Technological University
2. Zeyi Chen
School of Physical and Mathematical Sciences, Nanyang Technological University
3. Ariel Neufeld
School of Physical and Mathematical Sciences, Nanyang Technological University

Abstract

We propose a provably convergent algorithm for approximating Wasserstein barycenter of continuous and non-parametric measures. Our algorithm is inspired by the fixed-point scheme of Álvarez-Esteban, del Barrio, Cuesta-Albertos, and Matrán (2016), which begins with an initial measure and iteratively updates it via its pushforward by the mean of optimal transport (OT) maps to the input measures. However, the convergence of their scheme relies on obtaining exact OT maps which is computationally intractable for general non-parametric measures. Hence, we develop consistent estimators of OT maps via shape-constrained least squares regression, and replace the OT maps in the fixed-point scheme with their estimated counterparts. This gives rise to a stochastic fixed-point algorithm which is provably convergent to the true barycenter. Specifically, in order to obtain consistent OT map estimators, we develop tailored approximation techniques for preserving the regularity of both the true OT maps and the estimated OT maps throughout the iterations. Moreover, our algorithm does not restrict the support of the barycenter and can be implemented in a distributed computing environment. These properties make it suitable for large-scale information aggregation problems, e.g., multi-expert consensus in recommender systems and distributed sensor networks. In our numerical experiment, we showcase the practicality and efficiency of our algorithm for expert consensus on probabilistic forecasting.

Keywords

Status: accepted

Back to the list of papers