Research map / Learning theory and algorithms / Sample complexity
Optimal Coresets for Low-Dimensional Geometric Median
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a deterministic coreset construction of size roughly ε^(-d/(d+1)) for Euclidean geometric median in low dimensions, with a matching lower bound for coresets made of input points.
Problem
Coresets for the geometric median (1-median) in low-dimensional Euclidean space: the minimum size of a weighted subset preserving the sum of distances to any query point within (1±ε), where prior bounds were not tight.
Approach
Uses a polynomial/Alexander-style lemma giving signed weights in [-1,1] whose weighted distance sum decays as 1/|q|^c far from the cube, combined with a modified quad-tree that bootstraps repeated halving of the coreset; a discrepancy-theory argument yields the matching lower bound.
Key results
- Deterministic coreset of size Õ(2^{η d} ε^{-d/(d+1)}) for the Euclidean geometric median, matching the Ω(ε^{-d/(d+1)}) lower bound for input-point coresets up to polylog factors.
- Recovers the optimal Õ(√(ε^{-1})) bound for the line metric of Huang et al. 2023.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the deterministic coreset construction | Geometric median coreset · Low-dimensional Euclidean space | coreset size: ˜O(ε−d/(d+1)) vs. ˜O(ε−2d/(d+1)) | Helped |
| Use the deterministic coreset construction | Geometric median coreset · Low-dimensional Euclidean space | coreset size: ˜O(ε−d/(d+1)) vs. ˜O(√d · ε−1) | Helped |
| Restrict the coreset to input points | Geometric median coreset · Low-dimensional Euclidean space | coreset size: Ω(ε−d/(d+1)) | Mixed |
Surprising findings
- Coreset size is sublinear in 1/ε in low dimensions, improving on prior bounds that were linear for d≥2 in the plane (Õ(ε^{-1.5})).
Limitations
- Lower bound only holds when coreset points are chosen from the input points.
- Exponential dependence 2^{O(d)} on dimension in the upper bound from quad-tree construction.
- Results are purely theoretical with no experiments.
Experimental setup
Metrics: coreset size multiplicative error
Baselines: Cohen-Addad et al. 2021 coreset Huang et al. 2023 coreset Braverman et al. 2022 coreset
Builds on: Alexander discrepancy lower bound Cohen-Addad et al. high-dimensional coresets Bravermann et al. low-dimensional coresets
Closest papers by meaning
- Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers (NeurIPS 2025 · similarity 0.89)
- Faster Approximation Algorithms for k-Center via Data Reduction (ICML 2025 · similarity 0.86)
- Universal Weak Coreset (AAAI 2024 · similarity 0.85)
- Private Geometric Median (NeurIPS 2024 · similarity 0.85)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.83)
- A Near Linear Query Lower Bound for Submodular Maximization (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.