BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//UIC
BEGIN:VEVENT
UID:2019092109402420190911T16150020190911T1705005d8698c8dca51@uic.edu
CATEGORIES:MEETING
STATUS:TENTATIVE
DTSTAMP:20190920T075119
DTSTART:20190911T161500
DTEND:20190911T170500
SUMMARY:Computer Science Theory Seminar: Algorithms for metric learning via contrastive embeddings, by Anastasios Sidiropoulos
DESCRIPTION:Anastasios Sidiropoulos (UIC): Algorithms for metric learning via contrastive embeddings We study the problem of supervised learning a metric space under discriminative constraints. Given a universe X and sets S, D of similar and dissimilar pairs in X, we seek to find a mapping f : X ? Y , into some target metric space M = (Y, ?), such that similar objects are mapped close together, and dissimilar objects are mapped to points are mapped far apart from each other. More generally, the goal is to find a mapping of maximum accuracy (that is, fraction of correctly classified pairs). We propose approximation algorithms for various versions of this problem, for the cases of Euclidean and tree metric spaces. For both of these target spaces, we obtain fully polynomial-time approximation schemes (FPTAS) for the case of perfect information. In the presence of imperfect information we present approximation algorithms that run in quasi-polynomial time (QPTAS). We also present an exact algorithm for learning line metric spaces with perfect information in polynomial time. Our algorithms use a combination of tools from metric embeddings and graph partitioning, that could be of independent interest. Based on joint work with Diego Ihara Centurion and Neshat Mohammadi. Please click here to make changes to, or delete, this seminar announcement.
LOCATION:1325 SEO Chicago IL
CLASS:PRIVATE
END:VEVENT
END:VCALENDAR