A Proof of Lemma 4.4: The first stage of Algorithm 1 outputs an entity-level coreset

For preparation, we first introduce an importance sampling framework for coreset construction, called the Feldman-Langberg framework [27, 13]. A.1 The Feldman-Langberg framework We first give the definition of query space and the corresponding coresets. The tuple (X, u, P, f) is called a query space. Specifically, if u(x) = 1 for all x X, we use (X, P, f) for simplicity. Intuitively, f represents a linear combination of weighted functions indexed by X, and P represents the ground set of f.