Multilevel Clustering via Wasserstein Means

Abstract

We propose a novel approach to the problem of multilevel clustering, which aims to simultaneously partition data in each group and discover grouping patterns among groups in a potentially large hierarchically structured corpus of data. Our method involves a joint optimization formulation over several spaces of discrete probability measures, which are endowed with Wasserstein distance metrics. We propose a number of variants of this problem, which admit fast optimization algorithms, by exploiting the connection to the problem of finding Wasserstein barycenters. Consistency properties are established for the estimates of both local and global clusters. Finally, experiment results with both synthetic and real data are presented to demonstrate the flexibility and scalability of the proposed approach.

arXiv commentProceedings of the ICML, 2017

References in corpus (3)

• Fast Computation of Wasserstein Barycenters
• Revisiting k-means: New Algorithms via Bayesian Nonparametrics
• Discrete Wasserstein Barycenters: Optimal Transport for Discrete Data

Cited by in corpus (38)

• Wasserstein barycenters are NP-hard to compute
• On the Complexity of Approximating Wasserstein Barycenter
• Minimax Confidence Intervals for the Sliced Wasserstein Distance
• Minimax Distribution Estimation in Wasserstein Distance
• On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm
• Screening Sinkhorn Algorithm for Regularized Optimal Transport
• Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm
• Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning
• Prototypical Partial Optimal Transport for Universal Domain Adaptation
• Outlier-Robust Optimal Transport
• Partial Optimal Transport with Applications on Positive-Unlabeled Learning
• Limit Distribution Theory for the Smooth 1-Wasserstein Distance with Applications
• Asymptotic Guarantees for Generative Modeling Based on the Smooth Wasserstein Distance
• Wasserstein barycenters can be computed in polynomial time in fixed dimension
• Interior-Point Methods Strike Back: Solving the Wasserstein Barycenter Problem
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Point-set Distances for Learning Representations of 3D Point Clouds
• Making transport more robust and interpretable by moving data through a small number of anchor points
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification
• On Linear Optimization over Wasserstein Balls
• Projection Robust Wasserstein Barycenters
• On Robust Optimal Transport: Computational Complexity and Barycenter Computation
• On Transportation of Mini-batches: A Hierarchical Approach
• Flow-based Alignment Approaches for Probability Measures in Different Spaces
• Improving Mini-batch Optimal Transport via Partial Transportation
• k-GANs: Ensemble of Generative Models with Semi-Discrete Optimal Transport
• Variational Wasserstein Barycenters for Geometric Clustering
• Entropic Gromov-Wasserstein between Gaussian Distributions
• Stability of Entropic Wasserstein Barycenters and application to random geometric graphs
• Matching Distributions via Optimal Transport for Semi-Supervised Learning
• Regularized Wasserstein Means for Aligning Distributional Data
• On Efficient Multilevel Clustering via Wasserstein Distances
• Causal Inference on Distribution Functions
• Selective information exchange in collaborative clustering using regularized Optimal Transport
• Riemannian-geometric generalizations of quantum fidelities and Bures-Wasserstein distance
• On Inductive Biases for Machine Learning in Data Constrained Settings
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity