Timezone: »
We introduce in this paper a novel strategy for efficiently approximating the Sinkhorn distance between two discrete measures. After identifying neglectable components of the dual solution of the regularized Sinkhorn problem, we propose to screen those components by directly setting them at that value before entering the Sinkhorn problem. This allows us to solve a smaller Sinkhorn problem while ensuring approximation with provable guarantees. More formally, the approach is based on a new formulation of dual of Sinkhorn divergence problem and on the KKT optimality conditions of this problem, which enable identification of dual components to be screened. This new analysis leads to the Screenkhorn algorithm. We illustrate the efficiency of Screenkhorn on complex tasks such as dimensionality reduction and domain adaptation involving regularized optimal transport.
Author Information
Mokhtar Z. Alaya (LITIS Lab, University Rouen Normandy)
Maxime Berar (Université de Rouen)
Gilles Gasso (LITIS - INSA de Rouen)
Alain Rakotomamonjy (Université de Rouen Normandie Criteo AI Lab)
More from the Same Authors
-
2020 Poster: Partial Optimal Transport with applications on Positive-Unlabeled Learning »
Laetitia Chapel · Mokhtar Z. Alaya · Gilles Gasso -
2019 Poster: Singleshot : a scalable Tucker tensor decomposition »
Abraham Traore · Maxime Berar · Alain Rakotomamonjy -
2017 Poster: Joint distribution optimal transportation for domain adaptation »
Nicolas Courty · Rémi Flamary · Amaury Habrard · Alain Rakotomamonjy -
2012 Poster: Multiple Operator-valued Kernel Learning »
Hachem Kadri · Alain Rakotomamonjy · Francis Bach · philippe preux -
2010 Workshop: New Directions in Multiple Kernel Learning »
Marius Kloft · Ulrich Rueckert · Cheng Soon Ong · Alain Rakotomamonjy · Soeren Sonnenburg · Francis Bach -
2009 Workshop: Temporal Segmentation: Perspectives from Statistics, Machine Learning, and Signal Processing »
Stephane Canu · Olivier Cappé · Arthur Gretton · Zaid Harchaoui · Alain Rakotomamonjy · Jean-Philippe Vert -
2008 Poster: Suppport Vector Machines with a Reject Option »
Yves Grandvalet · Joseph Keshet · Alain Rakotomamonjy · Stephane Canu -
2007 Workshop: Topology Learning: New Challenges At the Crossing of Machine Learning, »
Michael Aupetit · Frederic Chazal · Gilles Gasso · David Cohen-Steiner · pierre gaillard