Research map / Learning theory and algorithms / Sample complexity
Coresets for Classification – Simplified and Strengthened
Tung Mai, Cameron N Musco, Anup Rao
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| sample by l1 Lewis weights instead of uniform sampling | coreset for logistic/hinge loss · Webb Spam, Covertype, KDD Cup '99 | relative loss vs coreset size | Improved |
| sample by l1 Lewis weights instead of sqrt leverage scores | coreset for logistic/hinge loss · KDD Cup '99 (mu_y=35.18) | relative loss vs coreset size | Improved |
| sample by l1 Lewis weights instead of sqrt leverage scores | coreset for logistic/hinge loss · Covertype and Webb Spam | relative loss vs coreset size | No clear effect |
| add L2 regularization | uniform sampling coreset · Covertype and Webb Spam | relative loss at small coreset sizes | Improved |
| use Lewis weights instead of leverage-score-based sampling in theory | coreset size bound · logistic and hinge loss | number of samples: O~(d^3 mu^3/eps^4) -> O~(d mu^2/eps^2) | Improved |
Closest papers by meaning
- Simple Weak Coresets for Non-decomposable Classification Measures (AAAI 2024 · similarity 0.89)
- No Dimensional Sampling Coresets for Classification (ICML 2024 · similarity 0.89)
- Coresets for Near-Convex Functions (NeurIPS 2020 · similarity 0.88)
- Robust Sparsification via Sensitivity (ICML 2025 · similarity 0.86)
- Coresets for Multiple $\ell_p$ Regression (ICML 2024 · similarity 0.85)
- Stable Coresets via Posterior Sampling: Aligning Induced and Full Loss Landscapes (NeurIPS 2025 · similarity 0.85)
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.
