Research map / Learning theory and algorithms / Clustering
Robust Sparsification via Sensitivity
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.
Builds a framework for robust (outlier-resilient) strong coresets of sum-of-functions objectives by combining total sensitivity with a vanilla coreset, yielding size Õ(mT/ε)+Q, and applies it to robust regression, PCA and subspace embedding.
Problem
Constructing small strong coresets for robust objectives F^(m) that sum all but the m largest function values, for problems like regression, PCA, clustering and subspace embedding, where existing robust algorithms are high-order polynomial time.
Approach
Two-stage construction: repeatedly sample functions with probability 1/m and keep those with sensitivity Ω(ε) within the sample to capture all contributing (potential outlier) functions, then run a vanilla coreset on the rest and split its functions into copies with weights bounded by sensitivity-scaled m/ε, so that removing m outliers causes only O(ε) error.
Key results
- Coreset size Õ(md/ε)+Q for l2 subspace embedding is shown near-tight, with a matching Ω(md/ε) lower bound.
- On the Energy dataset with m=10, coresets of about 7-11% of rows give mean relative objective error of 0.01-0.02 and beat uniform sampling; runtime drops from 13.98s to about 1.5-1.9s.
- Robust regression algorithm achieves (1+14ε)-approximation in time d^O(m) e^O(m/ε) + O(nd).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed coreset instead of the full dataset for FastLTS | Robust regression with FastLTS · Energy | runtime (seconds): 13.981 -> 1.542 | Helped |
| Use the proposed coreset instead of the full dataset for FastLTS | Robust regression with FastLTS · Emission | runtime (seconds): 7.543 -> 0.280 | Helped |
| Use the proposed coreset rather than uniform sampling | Robust regression with FastLTS · Energy | robust objective relative error | Helped |
| Use the proposed coreset rather than uniform sampling | Robust regression with FastLTS · Emission | robust objective relative error | Helped |
| Use the proposed coreset rather than uniform sampling | Subspace embedding coreset · Energy | empirical distortion | Helped |
| Use the proposed coreset rather than uniform sampling | Subspace embedding coreset · Emission | empirical distortion | Helped |
Surprising findings
- Coreset size for the robust objective depends on the vanilla coreset only additively, so robustness costs roughly a factor m times total sensitivity.
Limitations
- Robust regression and PCA algorithms have runtime exponential in m/ε and d^O(m), which is impractical for large m.
- Experiments use a heuristic solver FastLTS, whose convergence is not theoretically understood.
- Solution approximation error in experiments is larger (about 0.25-0.3) than objective error on Energy dataset, attributed to high condition number.
Experimental setup
Datasets: Appliances Energy Prediction (UCI) Gas Turbine CO and NOx Emission (UCI)
Benchmarks: Appliances Energy Prediction Gas Turbine Emission
Metrics: empirical distortion parameter relative error of robust loss F^(m) relative error of solution in l2 and l-infinity norms runtime in seconds
Baselines: uniform sampling FastLTS Simonov et al. 2019
Builds on: sensitivity sampling leverage score sampling Feldman-Langberg coreset framework Simonov et al. 2019 robust PCA
Closest papers by meaning
- Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers (NeurIPS 2025 · similarity 0.89)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.86)
- No Dimensional Sampling Coresets for Classification (ICML 2024 · similarity 0.85)
- Coresets for Multiple $\ell_p$ Regression (ICML 2024 · similarity 0.85)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.85)
- Universal Weak Coreset (AAAI 2024 · similarity 0.84)
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.