Timezone: »
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)
-
2019 Poster: Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm »
Wed. Dec 11th 01:30 -- 03:30 AM Room East Exhibition Hall B + C #113
More from the Same Authors
-
2021 : Linear Convergence of Batch Greenkhorn for Regularized Multimarginal Optimal Transport »
Vladimir Kostic · Saverio Salzo · Massimiliano Pontil -
2022 Poster: Conditional Meta-Learning of Linear Representations »
Giulia Denevi · Massimiliano Pontil · Carlo Ciliberto -
2022 : Meta Optimal Transport »
Brandon Amos · Samuel Cohen · Giulia Luise · Ievgen Redko -
2022 Spotlight: Conditional Meta-Learning of Linear Representations »
Giulia Denevi · Massimiliano Pontil · Carlo Ciliberto -
2022 Spotlight: Lightning Talks 3B-1 »
Tianying Ji · Tongda Xu · Giulia Denevi · Aibek Alanov · Martin Wistuba · Wei Zhang · Yuesong Shen · Massimiliano Pontil · Vadim Titov · Yan Wang · Yu Luo · Daniel Cremers · Yanjun Han · Arlind Kadra · Dailan He · Josif Grabocka · Zhengyuan Zhou · Fuchun Sun · Carlo Ciliberto · Dmitry Vetrov · Mingxuan Jing · Chenjian Gao · Aaron Flores · Tsachy Weissman · Han Gao · Fengxiang He · Kunzan Liu · Wenbing Huang · Hongwei Qin -
2022 Poster: Learning Dynamical Systems via Koopman Operator Regression in Reproducing Kernel Hilbert Spaces »
Vladimir Kostic · Pietro Novelli · Andreas Maurer · Carlo Ciliberto · Lorenzo Rosasco · Massimiliano Pontil -
2021 : Carlo Ciliberto Q&A »
Carlo Ciliberto -
2021 : Carlo Ciliberto »
Carlo Ciliberto -
2021 : The NeurIPS 2021 BEETL Competition: Benchmarks for EEG Transfer Learning + Q&A »
Xiaoxi Wei · Vinay Jayaram · Sylvain Chevallier · Giulia Luise · Camille Jeunet · Moritz Grosse-Wentrup · Alexandre Gramfort · Aldo A Faisal -
2021 Poster: PSD Representations for Effective Probability Models »
Alessandro Rudi · Carlo Ciliberto -
2021 Poster: The Role of Global Labels in Few-Shot Classification and How to Infer Them »
Ruohan Wang · Massimiliano Pontil · Carlo Ciliberto -
2020 Poster: A Non-Asymptotic Analysis for Stein Variational Gradient Descent »
Anna Korba · Adil Salim · Michael Arbel · Giulia Luise · Arthur Gretton -
2020 Poster: Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits »
Arya Akhavan · Massimiliano Pontil · Alexandre Tsybakov -
2020 Poster: The Advantage of Conditional Meta-Learning for Biased Regularization and Fine Tuning »
Giulia Denevi · Massimiliano Pontil · Carlo Ciliberto -
2020 Poster: Estimating weighted areas under the ROC curve »
Andreas Maurer · Massimiliano Pontil -
2020 Poster: The Wasserstein Proximal Gradient Algorithm »
Adil Salim · Anna Korba · Giulia Luise -
2020 Poster: Structured Prediction for Conditional Meta-Learning »
Ruohan Wang · Yiannis Demiris · Carlo Ciliberto -
2020 Poster: Exploiting MMD and Sinkhorn Divergences for Fair and Transferable Representation Learning »
Luca Oneto · Michele Donini · Giulia Luise · Carlo Ciliberto · Andreas Maurer · Massimiliano Pontil -
2019 Poster: Online-Within-Online Meta-Learning »
Giulia Denevi · Dimitris Stamos · Carlo Ciliberto · Massimiliano Pontil -
2019 Poster: Localized Structured Prediction »
Carlo Ciliberto · Francis Bach · Alessandro Rudi -
2018 Poster: Bilevel learning of the Group Lasso structure »
Jordan Frecon · Saverio Salzo · Massimiliano Pontil -
2018 Poster: Learning To Learn Around A Common Mean »
Giulia Denevi · Carlo Ciliberto · Dimitris Stamos · Massimiliano Pontil -
2018 Spotlight: Bilevel learning of the Group Lasso structure »
Jordan Frecon · Saverio Salzo · Massimiliano Pontil -
2018 Poster: Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance »
Giulia Luise · Alessandro Rudi · Massimiliano Pontil · Carlo Ciliberto -
2018 Poster: Manifold Structured Prediction »
Alessandro Rudi · Carlo Ciliberto · Gian Maria Marconi · Lorenzo Rosasco -
2017 : An Efficient Method to Impose Fairness in Linear Models »
Massimiliano Pontil · John Shawe-Taylor -
2017 Workshop: Workshop on Prioritising Online Content »
John Shawe-Taylor · Massimiliano Pontil · Nicolò Cesa-Bianchi · Emine Yilmaz · Chris Watkins · Sebastian Riedel · Marko Grobelnik -
2017 Poster: Consistent Multitask Learning with Nonlinear Output Relations »
Carlo Ciliberto · Alessandro Rudi · Lorenzo Rosasco · Massimiliano Pontil -
2016 Poster: A Consistent Regularization Approach for Structured Prediction »
Carlo Ciliberto · Lorenzo Rosasco · Alessandro Rudi -
2016 Poster: Mistake Bounds for Binary Matrix Completion »
Mark Herbster · Stephen Pasteris · Massimiliano Pontil -
2015 : The Benefit of Multitask Representation Learning »
Massimiliano Pontil -
2014 Poster: Spectral k-Support Norm Regularization »
Andrew McDonald · Massimiliano Pontil · Dimitris Stamos -
2013 Workshop: New Directions in Transfer and Multi-Task: Learning Across Domains and Tasks »
Urun Dogan · Marius Kloft · Tatiana Tommasi · Francesco Orabona · Massimiliano Pontil · Sinno Jialin Pan · Shai Ben-David · Arthur Gretton · Fei Sha · Marco Signoretto · Rajhans Samdani · Yun-Qian Miao · Mohammad Gheshlaghi azar · Ruth Urner · Christoph Lampert · Jonathan How -
2013 Workshop: Output Representation Learning »
Yuhong Guo · Dale Schuurmans · Richard Zemel · Samy Bengio · Yoshua Bengio · Li Deng · Dan Roth · Kilian Q Weinberger · Jason Weston · Kihyuk Sohn · Florent Perronnin · Gabriel Synnaeve · Pablo R Strasser · julien audiffren · Carlo Ciliberto · Dan Goldwasser -
2013 Poster: A New Convex Relaxation for Tensor Completion »
Bernardino Romera-Paredes · Massimiliano Pontil -
2012 Poster: Optimal kernel choice for large-scale two-sample tests »
Arthur Gretton · Bharath Sriperumbudur · Dino Sejdinovic · Heiko Strathmann · Sivaraman Balakrishnan · Massimiliano Pontil · Kenji Fukumizu -
2010 Spotlight: A Family of Penalty Functions for Structured Sparsity »
Charles A Micchelli · Jean M Morales · Massimiliano Pontil -
2010 Poster: A Family of Penalty Functions for Structured Sparsity »
Charles A Micchelli · Jean M Morales · Massimiliano Pontil -
2008 Poster: Fast Prediction on a Tree »
Mark Herbster · Massimiliano Pontil · Sergio Rojas Galeano -
2008 Oral: Fast Prediction on a Tree »
Mark Herbster · Massimiliano Pontil · Sergio Rojas Galeano -
2008 Poster: On-Line Prediction on Large Diameter Graphs »
Mark Herbster · Massimiliano Pontil · Guy Lever -
2007 Spotlight: A Spectral Regularization Framework for Multi-Task Structure Learning »
Andreas Argyriou · Charles A. Micchelli · Massimiliano Pontil · Yiming Ying -
2007 Poster: A Spectral Regularization Framework for Multi-Task Structure Learning »
Andreas Argyriou · Charles A. Micchelli · Massimiliano Pontil · Yiming Ying -
2006 Poster: Prediction on a Graph with a Perceptron »
Mark Herbster · Massimiliano Pontil -
2006 Spotlight: Prediction on a Graph with a Perceptron »
Mark Herbster · Massimiliano Pontil -
2006 Poster: Multi-Task Feature Learning »
Andreas Argyriou · Theos Evgeniou · Massimiliano Pontil