Variational problems on graphs and their continuum limits
Dejan Slepcev, Carnegie Mellon University
Abstract: We will discuss variational problems arising in machine
learning and their limits as the number of data points goes to
infinity. Consider point clouds obtained as random samples of an
underlying "ground-truth" measure. Graph representing the point
cloud is obtained by assigning weights to edges based on the
distance between the points.
Many machine learning tasks, such as clustering and classification,
can be posed as minimizing functionals on such graphs. We
consider functionals involving graph cuts and graph laplacians and
their limits as the number of data points goes to infinity. In
particular we establish under what conditions the minimizers of
discrete problems have a well defined continuum limit, and
characterize the limit.
The talk is primarily based on joint work with Nicolas Garcia
Trillos, as well as on works with Xavier Bresson, Moritz Gerlach,
Matthias Hein, Thomas Laurent, James von Brecht and Matt Thorpe.