CMU-CS-21-147.pdf (1.4 MB)
Download file

Machine Learning: Metrics and Embeddings

Download (1.4 MB)
posted on 04.05.2022, 18:56 by Timothy ChuTimothy Chu

In this thesis, we analyze new theories of clustering, one of the most fundamental tasks in machine learning. We use methods drawing from multiple disciplines, including metric embeddings, spectral algorithms, and group representation theory.

1.We propose a metric that adapts to the shape of data, and show how to quickly compute it. These metrics may be useful for improving k-means clustering methods.

2. We build a spectral partition method with provable theoretical guarantees. This may lead to more theoretically principled spectral clustering methods, as existing methods do not have any such guarantees. Spectral clustering is one of the most popular methods of clustering.

3. We classify all Manhattan distance kernels. Kernel methods are one of the oldest and most established methods of clustering data. This result is a Manhattan distance analog of one of the fundamental results on machine learning kernels. 

Each of these contributions answers natural questions in machine  learning theory. We develop multidisciplinary tools from disciplines ranging from linear algebra to group theory, and combine these with key ideas from metric embeddings and computational geometry.




Degree Type



Computer Science

Degree Name

  • Doctor of Philosophy (PhD)


Gary Miller

Usage metrics