Research map / Learning theory and algorithms / Sample complexity
Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers
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.
Constructs robust geometric median coresets without the O(m) outlier term: size Õ(ε^-2 min{ε^-2,d}) when n≥4m, and an optimal 1D coreset of size Õ(ε^-1/2 + (m/n)ε^-1), via a non-component-wise error analysis.
Problem
Coreset size for robust geometric median (and robust (k,z)-clustering) in Euclidean space, where prior coreset sizes contain an O(m) term in the number of outliers m.
Approach
Instead of component-wise (bucket-wise) error analysis that forces all outliers into the coreset, it treats the cost error as one entity and integrates derivative differences as the center moves; in general d, it uniformly samples outlier candidates and uses ball range-space approximation to bound outlier-misalignment error.
Key results
- For d=1 the coreset size is Õ(ε^-1/2 + (m/n)ε^-1) with matching lower bound Ω(ε^-1/2 + (m/n)ε^-1), removing the O(m) term when n≥4m.
- General d: coreset size Õ(ε^-2 min{ε^-2,d}) in O(nd) time when n≥4m, eliminating the O(m) term from prior O(m)+Õ(ε^-2 min{ε^-2,d}) bounds.
- On Census1990, the method reaches empirical error 0.012 at coreset size 1000 while the baseline needs size 2300 for error slightly above 0.013.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Eliminate the O(m) additive coreset-size term when n≥4m | Robust geometric median coreset · Robust geometric median, general d | coreset size: O(m)+\tilde{O}(\varepsilon^{-2}\cdot \min\{\varepsilon^{-2},d\}) -> \tilde{O}(\varepsilon^{-2} \min\left\{\varepsilon^{- | Helped |
| Use the optimal 1D construction with size depending on m/n rather than an additive O(m) term | Robust geometric median coreset · Robust geometric median, d=1, n≥4m | coreset size: O(m)+\tilde{O}(\varepsilon^{-2}) -> \tilde{O}(\varepsilon^{-\frac{1}{2}}+\frac{m}{n}\varepsilon^{-1}) | Helped |
| Apply the proposed coreset method instead of the baseline | Robust geometric median · Census1990 | empirical error: 0.012 vs slightly higher than 0.013 | Helped |
| Use the proposed robust (k,z)-clustering coreset under the stated data assumption | Robust (k,z)-clustering coreset · Robust (k,z)-clustering, under Assumption | coreset size: O(m)+\tilde{O}(k^2 \varepsilon^{-2z} \min\{\varepsilon^{-2}, d\}) -> \tilde{O}(k^2\varepsilon^{-2z} \min\left\{\varepsil | Helped |
Surprising findings
- A lower bound of Ω(m/(n-m)) shows that eliminating the O(m) term is impossible when n-m is small, so the n-m=Ω(n) condition is necessary.
Limitations
- Upper bound for general d (Õ(ε^-2 min{ε^-2,d})) is likely not optimal; the authors say their 1D bound is likely not optimal in the general-d case.
- Results for robust (k,z)-clustering require extra geometric assumptions (inlier cluster sizes ≥4m, bounded remote inliers).
Experimental setup
Datasets: Census1990 PageBlocks
Benchmarks: Census1990 six real-world datasets
Metrics: coreset size vs empirical error runtime
Baselines: prior robust geometric median coresets with O(m) term uniform sampling baseline
Builds on: vanilla 1D geometric median coreset Cohen-Addad et al. hierarchical sampling robust clustering coreset bucket-based 1D coreset construction
Closest papers by meaning
- Optimal Coresets for Low-Dimensional Geometric Median (ICML 2024 · similarity 0.89)
- Robust Sparsification via Sensitivity (ICML 2025 · similarity 0.89)
- Universal Weak Coreset (AAAI 2024 · similarity 0.88)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.87)
- Coresets for Clustering Under Stochastic Noise (NeurIPS 2025 · similarity 0.87)
- Faster Approximation Algorithms for k-Center via Data Reduction (ICML 2025 · similarity 0.86)
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.