Scalable Combinatorial Algorithms for Optimal Transport Based Similarity Metrics

Optimal Transport (OT), also known as Wasserstein distance, is a valuable metric for comparing probability distributions. Owing to its appealing statistical properties, researchers in various fields, such as machine learning, use OT within applications. However, computing both exact and approximate OT is computationally expensive and impractical for large datasets. Furthermore, OT is sensitive to small noise in the input distributions. In this document, we propose to use combinatorial methods to design scalable and noise-resistant solutions for OT. We present four key contributions in this work. First, we introduce a novel combinatorial parallel algorithm for approximating OT, which achieves a parallel time complexity of O(log n/varepsilon²), where $n$ is the input size and $varepsilon$ is the addtitive error, Our algorithm outperforms the state-of-the-art in experiments. Second, we propose a new concept, OT-profile, representing the function of minimum partial optimal transport cost sigma_alpha versus the transported mass $alpha$. This can be used to identify outliers in real-world data. The utility of OT-profile is demonstrated in outlier detection and PU-learning jobs and outperforms the state-of-the-art. Third, building upon the OT-profile, we propose a new OT-based metric for comparing distributions that is more robust to noise. This metric preserves desirable properties while reducing its sensitivity to noise for high $p$ values, providing a robust solution for real-world datasets. Lastly, we have developed a Python library that integrates our algorithms and methods into a user-friendly framework, making it easier for practitioners to adopt our methods. Our work enhances the computational efficiency and robustness of OT, making it practical for machine learning applicaitons.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Computer Science & Applications

Department dc:contributor.department

Computer Science and#38; Applications

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2024

Author dc:creator

• Zhang, Kaiyi

Chair dc:contributor.committeechair

• Raghvendra, Sharath

Committee members dc:contributor.committeemember

• Karpatne, Anuj
• Tripathy, Chittaranjan
• Ji, Bo
• Heath, Lenwood S.
• Zhang, Liqing

• Combinatorial Optimization
• Optimal Transport
• Wasserstein distance

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Dc Identifier Other

vt_gsexam:41577

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/123647