Website

An overview of metric embeddings and metric repair (and why they matter). In this first lecture, I will introduce the notion of metric embeddings and explain some basic mathematical and algorithmic results. Next, I will define the metric repair problem which captures the question, “What happens if we don’t have a metric to begin with?!” Fortunately and unfortunately, this problem is both hard and hard to approximate, making it an interesting algorithmic question in its own right.

Project and Forget and its applications. In the second lecture, I will describe a general optimization framework for solving metric-constrained problems which arise from metric embeddings and repair problems. This optimization method can be used to solve huge problems, problems so large that one cannot write down all of the (inequality) constraints. Finally, I will discuss its application to transfer learning and optimal transport.

Extensions to random weighted graphs and trees. In the third lecture, I will discuss on-going work that tries to determine how to solve metric repair problems on average graphs. In doing so, we develop an interesting family of random graphs and discuss some preliminary structural results for this family.