# Multi-Objective Weighted Sampling

arXiv: https://arxiv.org/abs/1509.07445 · HTML: https://mlsanity.com/paper/1509.07445/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Sep 2015.

## Built on by (most cited first, 1 of 1)

- [Hot PATE: Private Aggregation of Distributions for Diverse Task](https://mlsanity.com/paper/2312.02132/) (2023)

## Abstract (arXiv)

em Multi-objective samples are powerful and versatile summaries of large data sets. For a set of keys x∈ X and associated values fx ≥ 0, a weighted sample taken with respect to f allows us to approximate em segment-sum statistics Sum(f;H) = sumx∈ H fx, for any subset H of the keys, with statistically-guaranteed quality that depends on sample size and the relative weight of H. When estimating Sum(g;H) for gnot=f, however, quality guarantees are lost. A multi-objective sample with respect to a set of functions F provides for each f∈ F the same statistical guarantees as a dedicated weighted sample while minimizing the summary size. We analyze properties of multi-objective samples and present sampling schemes and meta-algortithms for estimation and optimization while showcasing two important application domains. The first are key-value data sets, where different functions f∈ F applied to the values correspond to different statistics such as moments, thresholds, capping, and sum. A multi-objective sample allows us to approximate all statistics in F. The second is metric spaces, where keys are points, and each f∈ F is defined by a set of points C with fx being the service cost of x by C, and Sum(f;X) models centrality or clustering cost of C. A multi-objective sample allows us to estimate costs for each f∈ F. In these domains, multi-objective samples are often of small size, are efficiently to construct, and enable scalable estimation and optimization. We aim here to facilitate further applications of this powerful technique.