報告題目：Sampling-based Methods for Inner Product Sketching

報告時間：2024年8月26日14:30-15:30

報告地點：437bwin必贏國際官網B404

報告人：Christopher Musco

報告人國籍：美國

報告人單位：New York University

報告人簡介：Christopher Musco is an assistant professor of Computer Science and Engineering at New York University. He is a member of NYU's Theoretical Computer Science group and the Visualization, Data Analysis, and Imaging Center (VIDA Center). His research focuses on the design and theoretical analysis of randomized algorithms with applications in computational mathematics, machine learning, and databases. Professor Musco's work has been funded by the US Department of Energy and National Science Foundation, including through an NSF CAREER Award.

報告摘要：I will discuss new "sketching'' methods that can accurately estimate the inner product between any two vectors based on a small compression (or "sketch") of those vectors. Sketches for estimating inner products find applications across databases (for join-size estimation, correlation estimation, and more) and machine learning (for model evaluation, similarity computation, and vector search). Prior state-of-the-art sketching methods for inner products are based on Johnson-Lindenstrauss (JL) random projection and related methods. In contrast, the methods I will discuss are based on an old and powerful technique called "coordinated random sampling". I will prove that our sampling-based sketches enjoy stronger worst-case theoretical guarantees than sketches based on JL projection, and also perform better in practice across a wide variety of applications.

邀請人：王勝