Timezone: »

Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm
Giulia Luise · Saverio Salzo · Massimiliano Pontil · Carlo Ciliberto

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #113

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.

Author Information

Giulia Luise (University College London)
Saverio Salzo (Istituto Italiano di Tecnologia)
Massimiliano Pontil (IIT & UCL)
Carlo Ciliberto (Imperial College London)

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

More from the Same Authors