Introduction to Coresets: How to Compute a Coreset?

Description

In this video, Alaa Maalouf, a Lead Coreset Researcher at DataHeroes, focuses on how to compute a Coreset. The video introduces the sensitivity or important sampling framework, which is a unified framework used by many papers to compute Coresets.

The framework involves computing a number called sensitivity for each point in the input data, which defines its importance or sensitivity. These sensitivities are then used to sample a certain number of points, called M, to form a Coreset. This Coreset, along with a weight function, approximates the cost of the input data with respect to a query space and cost function. The video also explains how the size of the Coreset, M, is determined by the approximation error, probability of success, total sensitivity, and complexity measure of the problem.