静5青年讲座 | Metric Clustering and MST...

Metric Clustering and MST with Strong and Weak Distance Oracles

报告人

Dr. Chen Wang

Rice University & Texas A&M University

时  间

2024年6月4日 星期二 10:30am

地  点

静园五院204

Host

孔雨晴 助理教授

 Abstract

I will discuss recent results of  -clustering and MST in a new weak-strong oracle model. In this model, for a fixed metric space  , we can compute distances in two ways: via a 'strong' oracle that returns exact distances  , and a 'weak' oracle that returns distances  which may be arbitrarily corrupted with some probability. This model captures the increasingly common trade-off between employing both an expensive similarity model (e.g. a large-scale embedding model) and a less accurate but cheaper model. Hence, the goal is to make as few queries to the strong oracle as possible. We consider both 'point queries', where the strong oracle is queried on a set of points  and returns  for all  , and 'edge queries' where it is queried for individual distances  .

Our main contributions are optimal algorithms and lower bounds for clustering and Minimum Spanning Tree (MST) in this model. For  -centers,  -median, and  -means, we give constant factor approximation algorithms with only  strong oracle point queries, and prove that  queries are required for any bounded approximation. For edge queries, our upper and lower bounds are both  . Surprisingly, for the MST problem, we give an  approximation algorithm using no strong oracle queries at all, and we prove a matching  lower bound which holds even if  strong oracle point queries are allowed.

Based on a joint work with MohammadHossein Bateni, Prathamesh Dharangutte, and Rajesh Jayaram on COLT 2024.

Biography

Chen Wang is a postdoctoral researcher hosted jointly by Vladimir (Vova) Braverman at Rice University and Samson Zhou at Texas A&M University. His research interests mainly focus on the intersections between Theoretical Computer Science and Machine Learning. In particular, he is interested in the theoretical foundations of practical learning problems and the design of algorithms with rigorous guarantees therein. More broadly, he is also interested in streaming algorithms and lower bounds, graph algorithms, statistical learning theory, and data processing privacy.

Chen obtained his Ph.D. at Rutgers University, where he was advised by Sepehr Assadi. He is the recipient of the Rutgers SGS Research & Travel Award, and he obtained nominations from Rutgers to Google Ph.D. fellow and Apple ML/AI scholar. He also received travel awards from various conferences, including SODA 2022, Neurips 2022, Neurips 2023, and STOC 2023.

往 期 讲 座

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”查看海报