Optimal Coresets for Low-Dimensional Geometric Median
Abstract
We investigate coresets for approximating the cost with respect to median queries. In this problem, we are given a set of points $P\subset \mathbb{R}^d$ and median queries are $\sum_{p\in P} ||p-c||$ for any point $c\in \mathbb{R}^d$. Our goal is to compute a small weighted summary $S\subset P$ such that the cost of any median query is approximated within a multiplicative $(1\pm\varepsilon)$ factor. We provide matching upper and lower bounds on the number of points contained in $S$ of the order $\tilde{\Theta}\left(\varepsilon^{-d/(d+1)}\right)$.
Cite
Text
Afshani and Schwiegelshohn. "Optimal Coresets for Low-Dimensional Geometric Median." International Conference on Machine Learning, 2024.Markdown
[Afshani and Schwiegelshohn. "Optimal Coresets for Low-Dimensional Geometric Median." International Conference on Machine Learning, 2024.](https://mlanthology.org/icml/2024/afshani2024icml-optimal/)BibTeX
@inproceedings{afshani2024icml-optimal,
title = {{Optimal Coresets for Low-Dimensional Geometric Median}},
author = {Afshani, Peyman and Schwiegelshohn, Chris},
booktitle = {International Conference on Machine Learning},
year = {2024},
pages = {262-270},
volume = {235},
url = {https://mlanthology.org/icml/2024/afshani2024icml-optimal/}
}