Research map / Learning theory and algorithms / Prediction and decision losses
Simple Weak Coresets for Non-decomposable Classification Measures
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.
Shows that stratified uniform sampling yields weak coresets for F1 score and MCC on classification, with matching lower bounds showing strong coresets need size n, and empirically matches more sophisticated coreset methods.
Problem
Coresets have been limited to decomposable losses in supervised classification; non-decomposable measures such as F1 score and MCC lack coreset guarantees, and optimizing them on large data is costly.
Approach
Stratified uniform sampling (sampling uniformly within each class) gives weak coresets for F1 and MCC over a query set containing high-F1/high-tp classifiers, using VC-dimension-based uniform convergence bounds; lower bounds show strong coresets require size n, so uniform sampling is essentially optimal.
Key results
- Uniform sampling coresets give F1 and MCC comparable to or better than leverage score, Lewis score, and k-means coresets across logistic regression, SVM, and MLP on CoverType, KDD Cup '99 and Adult.
- On the Bank Marketing dataset, uniform sampling at 10% reaches F1 0.4400 with LR, 0.5290 with DT and 0.5972 with GB, comparable to Lewis sampling.
- Coreset construction with uniform sampling takes about 0.014 s on CoverType versus 2.49 s for Lewis score at 10% of data.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use stratified uniform rather than the other tested coreset sampling strategies | Logistic Regression on Bank Marketing · Bank Marketing, 2% coreset | F1 Score: 0.3125 (leverage), 0.4002 (kmeans), 0.4346 (lewis), 0.4331 (uniform) | Mixed |
| Use stratified uniform rather than the other tested coreset sampling strategies | Decision Tree on Bank Marketing · Bank Marketing, 10% coreset | F1 Score: 0.4898 (leverage), 0.5216 (lewis), 0.5184 (kmeans), 0.5290 (uniform) | Helped |
| Use stratified uniform rather than the other tested coreset sampling strategies | Gradient Boosting on Bank Marketing · Bank Marketing, 10% coreset | F1 Score: 0.5862 (leverage), 0.5946 (lewis), 0.5822 (kmeans), 0.5972 (uniform) | Helped |
| Increase coreset size from 2% to 10% using uniform sampling | Gradient Boosting on Bank Marketing · Bank Marketing | F1 Score: 0.5623 -> 0.5972 | Helped |
| Use stratified uniform rather than the other tested coreset sampling strategies | Logistic Regression on Bank Marketing · Bank Marketing, 2% coreset | MCC Score: 0.2237 (leverage), 0.3123 (kmeans), 0.3531 (lewis), 0.3512 (uniform) | Mixed |
| Increase coreset size from 2% to 10% using uniform sampling | Gradient Boosting on Bank Marketing · Bank Marketing | MCC Score: 0.5030 -> 0.5466 | Helped |
Surprising findings
- Uniform sampling, the simplest strategy, matches or beats sophisticated sensitivity-based coreset methods empirically.
- Strong coresets for F1 and MCC require size n, so no sampling scheme can do much better than uniform sampling in the strong sense.
Limitations
- Guarantees are weak coresets that hold only for a restricted query set Q_gamma (high F1 or tp/tn conditions), not all classifiers.
- MCC bound includes an additive error term and the coreset-size bound depends on the VC dimension of the query class and class ratio.
- Theory covers F1 and MCC only; AUC-ROC and other measures are left open.
Experimental setup
Datasets: CoverType KDD Cup '99 Adult Bank Marketing
Benchmarks: CoverType KDD Cup '99 Adult Bank Marketing
Metrics: F1 score MCC coreset construction time
Baselines: leverage score sampling Lewis score sampling k-means coreset
Builds on: sensitivity sampling coresets uniform convergence bounds for relative error (Li et al. style)
Closest papers by meaning
- No Dimensional Sampling Coresets for Classification (ICML 2024 · similarity 0.91)
- Universal Weak Coreset (AAAI 2024 · similarity 0.86)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.86)
- Robust Sparsification via Sensitivity (ICML 2025 · similarity 0.84)
- Focal-SAM: Focal Sharpness-Aware Minimization for Long-Tailed Classification (ICML 2025 · similarity 0.84)
- Coresets for Clustering Under Stochastic Noise (NeurIPS 2025 · 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.