Research

My research focuses on designing and implementing algorithms that work with Bregman divergences and the geometry that they generate. Additionally, I research algorithms pertaining to persistent homology, a tool from Topological Data Analysis.

More broadly, I am also interested in machine learning and image processing.

Bregman Divergences:

Bregman divergences are distance measures which are generally not symmetric and do not satisfy the triangle inequality. Members of this family have been shown to work well for machine learning tasks. Some examples include the Kullback–Leibler divergence (also known as relative entropy), often used for analyzing text and images, the Itakura–Saito divergence, popularly used for analyzing speech and sound data, and the squared Euclidean distance. However, since they do not satisfy the usual assumptions from metrics, the usual algorithms proofs for correctness often do not apply directly.

Many computational geometry tools have been shown to work with Bregman divergences despite their unintuitive behaviors. A select few are shown below:

• Banerjee, Merugu, Dhillon, and Ghosh have shown that the K-means algorithm works for general Bregman divergences
• Edelsbrunner and Wagner have shown that persistence homology tools can be used when the filtration is generated by Bregman divergences rather than the Euclidean distance

Publications

The projects above were funded by the 2022 Google Research Scholar Award in Algorithms and Optimization.

Computing Representatives of Persistent Homology Generators with a Double Twist

 – Tuyen Pham, Hubert Wagner

Accepted by Canadian Conference on Computational Geometry (CCCG) 2023 – Volume 35, 283-290. (ArXiv)

Storing the complete simplicial complex for large data sets grows is often infeasible and thus many applications for persistent homology will instead restrict the complex to a lower dimensional skeleta. This paper provides a faster algorithm for computing generators of cycle representatives for these low dimensional skeleta restrictions. The returned generators are shown to be the same as those returned by the standard persistent homology algorithms introduced by Edelsbrunner, Letscher and Zomorodian. Experiments show that our algorithm performs up to 200 times faster.

Bregman-Hausdorff divergence: strengthening the connections between computational geometry and machine learning

– Tuyen Pham Hana Dal Poz Kouřimská, Hubert Wagner

Publishing in Machine Learning and Knowledge Extraction 2025 — Extravaganza Feature Papers on Hot Topics in Machine Learning and Knowledge Extraction (ArXiv)

We propose an extension of the Hausdorff distance from metric spaces to spaces equipped with asymmetric distance measures. Specifically, we focus on the family of Bregman divergences, which includes the popular Kullback–Leibler divergence (also known as relative entropy).

As a proof of concept, we use the resulting Bregman–Hausdorff divergence to compare two collections of probabilistic predictions produced by different machine learning models trained using the relative entropy loss. The algorithms we propose are surprisingly efficient even for large inputs with hundreds of dimensions.
In addition to the introduction of this technical concept, we provide a survey. It outlines the basics of Bregman geometry, as well as computational geometry algorithms. We focus on algorithms that are compatible with this geometry and are relevant for machine learning.

Fast Kd-trees for the Kullback–Leibler Divergence and other Decomposable Bregman Divergences

– Tuyen Pham, Hubert Wagner

Accepted by Algorithms and Data Structures Symposium (WADS) 2025 (ArXiv)

First, we prove that Kd-trees can be extended to spaces in which the distance is measured with an arbitrary Bregman divergence. Perhaps surprisingly, this shows that the triangle inequality is not necessary for correct pruning in Kd-trees. Second, we offer an efficient algorithm and C++ implementation for nearest neighbour search for decomposable Bregman divergences.

The implementation supports the Kullback–Leibler divergence (relative entropy) which is a popular distance between probability vectors and is commonly used in statistics and machine learning. This is a step toward broadening the usage of computational geometry algorithms. Our benchmarks show that our implementation efficiently handles both exact and approximate nearest neighbour queries. Compared to a naive approach, we achieve two orders of magnitude speedup for practical scenarios in dimension up to 100. Our solution is simpler and more efficient than competing methods.