| Date: | February 7, 2020 |
| Time: | 3:00pm |
| Location: | BLOC220 |
| Speaker: | Ilya Razenshteyn, Microsoft Research Redmond |
| Title: | Spectral Partitioning of Metric Spaces |
| Abstract: | I will show how to build efficient nearest neighbor search data structures for general metric spaces using a novel randomized partitioning procedure which is closely related to metric spectral gaps.
Based on joint work with Alex Andoni, Assaf Naor, Sasho Nikolov and Erik Waingarten. |
|
| Date: | February 20, 2020 |
| Time: | 3:00pm |
| Location: | BLOC220 |
| Speaker: | Anastasios Sidiropoulos, University of Illinois at Chicago, Theory Group |
| Title: | Robust metric learning via geometric approximation algorithms |
| Abstract: | We study the problem of 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 host metric space M = (Y, ρ), such that similar objects are mapped close together, and dissimilar objects are mapped to points that are far apart from each other. More generally, the goal is to find a mapping of maximum accuracy (that is, fraction of correctly classified examples). We propose approximation algorithms for various versions of this problem, for the cases of Euclidean and tree metric spaces, and for both linear and non-linear mappings. Our problem formulation leads to algorithms that are shown to be robust against poisoning attacks when learning Mahalanobis metric spaces. Finally, we also discuss the problem of learning Mahalanobis metric spaces using depth-2 neural networks.
Based on joint works with Diego Ihara Centurion, Bohan Fan, Neshat Mohammadi and Francesco Sgherzi. |
|
| Date: | February 28, 2020 |
| Time: | 3:00pm |
| Location: | BLOC220 |
| Speaker: | Alex Andoni, Columbia University, Data Science Institute |
| Title: | Estimating distances in a graph metric, in parallel |
| Abstract: | We show how to estimate distances (and shortest paths) between nodes in
undirected graphs using a fast parallel algorithm. Our algorithm
achieves $(1+\epsilon)$ approximation, poly(log n) time and m*poly(log
n) work for n-nodes m-edges graphs --- a question open since Cohen's
result from STOC'94.
One of our main tools is a new notion of low hop emulators: a
poly(log n)-approximate emulator graph in which every shortest path has
at most O(loglog n) hops (edges). Direct applications of this tool are
efficient parallel constructions of Bourgain's embedding, metric tree
embedding, and low diameter decomposition.
To obtain the better approximation ratio, we introduce compressible
preconditioners and apply it inside Sherman's framework (SODA'17) to
solve the more general problem of transportation in graphs
(uncapacitated minimum cost flow). As a consequence, it also improves
the state-of-the-art sequential running time for the latter.
Joint work with Cliff Stein, Peilin Zhong. To appear in STOC'20. |
|
| Date: | March 13, 2020 |
| Time: | 3:00pm |
| Location: | BLOC220 |
| Title: | Spring Break |
|
| Date: | March 27, 2020 |
| Time: | 3:00pm |
| Location: | BLOC220 |
| Speaker: | András Zsák, Peterhouse College, University of Cambridge |
| Title: | canceled due to the COVID-19 pandemic |
|
| Date: | April 10, 2020 |
| Time: | 3:00pm |
| Location: | BLOC220 |
| Speaker: | Yury Makarychev, Toyota Technological Institute at Chicago and Univ. of Chicago |
| Title: | canceled due to the COVID-19 pandemic |
|
| Date: | April 24, 2020 |
| Time: | 3:00pm |
| Location: | BLOC220 |
| Speaker: | Alejandro Chavez Dominguez, University of Oklahoma |
| Title: | canceled due to the COVID-19 pandemic |
|
Menu