Special Colloquium
COLLOQUIUMS
Speaker:
Anna Gilbert - Yale University
Title: Metric representations: Algorithms and Geometry
Abstract: Given a data set or a set of distances amongst data points, determining what combinatorial representation is most “consistent” with the input distances or the metric that best captures the relevant geometric features of the data is a key step in many machine learning algorithms. We seek such representations to gain new insights into the data generation process or to uncover fundamental structures in the data (especially for scientific discovery). We may also seek representations that improve computational efficiency.
In this talk, we focus on a variety of metric representation problems. The first three are specific metric constrained problems, a class of optimization problems with metric constraints: metric nearness, weighted correlation clustering on general graphs, and metric learning. The fourth problem is sparse metric repair, a non-convex version of the metric nearness problem. The final problem seeks a combinatorial representation of data sets in the form of trees or sparse graphs (which we then embed into hyperbolic space).
Because of the large number of constraints in the metric constrained problems, however, these and other researchers have been forced to restrict either the kinds of metrics learned or the size of the problem that can be solved. We provide an algorithm, PROJECT AND FORGET, that uses Bregman projections with cutting planes, to solve metric constrained problems with many (possibly exponentially) inequality constraints.
We discuss the surprising features of the fourth problem, sparse metric repair problem; in one setting it has a simple polynomial time solution and in the other settings, it is fiendishly difficult. Finally, we end with something different. We learn combinatorial structures rather than metrics or data geometry. We then use those to embed the data sets into metric spaces.
This is joint work with a number of collaborators and students: Rishi Sonthalia (Univ. of Michigan), Lalit Jain (Univ. of Washington), Benjamin Raichel (Univ. of Texas-Dallas), and Greg van Buskirk (Univ. of Texas-Dallas).
Registration is required to receive the Zoom information