Luise, G; Salzo, S; Pontil, M; Ciliberto, C; (2019) Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm. In: Wallach, H and Larochelle, H and Beygelzimer, A and D'Alche-Buc, F and Fox, E and Garnett, R, (eds.) Proceedings of Advances in Neural Information Processing Systems 32 (NeurIPS 2019). NeurIPS Proceedings: Vancouver, Canada.

Preview

Text NeurIPS-2019-sinkhorn-barycenters-with-free-support-via-frank-wolfe-algorithm-Paper.pdf - Published Version Download (1MB) | Preview

Abstract

We present a novel algorithm to estimate the barycenter of arbitrary probability distributions with respect to the Sinkhorn divergence. Based on a Frank-Wolfe optimization strategy, our approach proceeds by populating the support of the barycenter incrementally, without requiring any pre-allocation. We consider discrete as well as continuous distributions, proving convergence rates of the proposed algorithm in both settings. Key elements of our analysis are a new result showing that the Sinkhorn divergence on compact domains has Lipschitz continuous gradient with respect to the Total Variation and a characterization of the sample complexity of Sinkhorn potentials. Experiments validate the effectiveness of our method in practice.

Download activity - last month

Export as JSONXMLCSV

Download activity - last 12 months

Export as XMLCSVJSON

Downloads by country - last 12 months

Export as CSVXMLJSON

Archive Staff Only

View Item