Research map / Learning theory and algorithms / Sample complexity
No Dimensional Sampling Coresets for Classification
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 the first dimension-free sensitivity-sampling coreset bounds for regularized classification (monotone loss plus 1/k ||w||^2 regularizer) by bounding Rademacher complexity of the sensitivity-augmented function class.
Problem
Coresets for regularized linear classification (logistic, sigmoid, SVM, ReLU losses) typically have sizes depending on dimension d and data size n; the paper asks whether coreset size can be independent of dimension and usable for iid samples from a distribution.
Approach
Replace the VC-dimension step in sensitivity sampling with a Rademacher complexity bound for the sensitivity-augmented family, and show that for well-behaved distributions with bounded second moment of the norm, total sensitivity is dimension-free, yielding coresets of size O(k^3/eps^2) (and O(k^3/(eps^2 sqrt(log k))) for logistic loss) with no dependence on d.
Key results
- Provides the first no-dimensional coreset for monotone-loss classification with regularization 1/k ||w||^2, of size O(k^3/eps^2), independent of dimension d.
- For logistic loss, the dimension-free bound improves by a sqrt(log k) factor, giving O(k^3/(eps^2 sqrt(log k))), and a dimension-dependent bound O(dk sqrt(log k)/eps^2) via VC/Rademacher arguments.
- Shows a Rademacher-complexity version of the sensitivity sampling theorem and a simpler Fubini-based proof of the VC-based relative-error lemma that handles infinite ground sets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Rademacher-complexity bound to obtain a dimension-independent coreset size | Regularized classification with sigmoid, SVM, and ReLU losses on bounded data · Regularized classification | coreset size: O\left(\frac{dk\log k}{\varepsilon^2}\right) -> O\left(\frac{k^3}{\varepsilon^2}\right) | Helped |
| Use the improved logistic-loss bound | Regularized logistic classification on bounded data · Regularized classification, logistic loss | coreset size: O\left(\frac{dk\sqrt{\log k}}{\varepsilon^2}\right) -> O\left(\frac{k^3}{\varepsilon^2\sqrt{\log k}}\right) | Helped |
| Use iid sampling from the data distribution under the stated bounded-data assumptions | Regularized classification with sigmoid, logistic, SVM, or ReLU loss · Regularized classification | coreset size | Helped |
Limitations
- No experiments; results are purely theoretical bounds and the authors state they do not provide new experimental evidence.
- Dimension-free bounds require well-behaved distributions with bounded second moment of the norm (or bounded support) and a regularization term; the k^3 dependence is large.
- Some bounds (e.g., ReLU, kernel cases) are stated with constants that depend on assumptions, and the text contains many typos and inconsistent statements.
Experimental setup
Baselines: Huggins et al. 2016 logistic coresets Munteanu et al. 2018 Lewis weights coresets Tolochinsky and Feldman 2018 Mai et al. 2021 uniform sampling for regularized loss Karnin et al. 2019 sensitivity sampling
Builds on: sensitivity sampling VC-dimension coreset bounds Talagrand contraction lemma McDiarmid inequality
Closest papers by meaning
- Simple Weak Coresets for Non-decomposable Classification Measures (AAAI 2024 · similarity 0.91)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.86)
- Robust Sparsification via Sensitivity (ICML 2025 · similarity 0.85)
- Small coresets via negative dependence: DPPs, linear statistics, and concentration (NeurIPS 2024 · similarity 0.85)
- Stable Coresets via Posterior Sampling: Aligning Induced and Full Loss Landscapes (NeurIPS 2025 · similarity 0.84)
- 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.