Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm

By Giulia Luise, Saverio Salzo, Massimiliano Pontil, Carlo Ciliberto. 2019

71 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, background): “…Miech x k +1 = (1 − γ t ) x k + γ k v k ⊲ Convex update 5: end for et al. 2018; Lacoste-Julien et al. 2015b; Courty et al. 2016; Paty et al. 2019; Luise et al. 2019]; however, many open questions remain in designing such optimal algorithmic schemes ( e.g. [Braun et al. 2017; Kerdreux et al.…”
Automatic Text Evaluation through the Lens of Wasserstein Barycenters (2021, background): “To make it computationally tractable, the measure μ is often constrained to be a discrete measure with free (Cuturi and Doucet, 2014; Álvarez Esteban et al., 2016; Cuturi and Peyré, 2016; Luise et al., 2019) or fixed support (Benamou et al.”
Projection-Free Optimization on Uniformly Convex Sets (2020, background): “…rules in RKHS (Bach et al., 2012; Lacoste-Julien et al., 2015; Futami et al., 2019), optimal transport (Courty et al., 2016; Vayer et al., 2018; Paty and Cuturi, 2019; Luise et al., 2019), and many others. x t +1 = (1 − γ t ) x t + γ t v t (cid:46) Convex update 5: end for Uniform Convexity.”