Research map / Learning theory and algorithms / Sample complexity
Gradient-based Sampling: An Adaptive Importance Sampling for Least-squares
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| gradient-based sampling instead of leverage-based sampling | least-squares subsampling · CASP and NEWS real data (Poisson sampling) | MSE | Helped |
| Poisson sampling instead of sampling with replacement (ablation) | gradient-based sampling · NEWS real data | MSE: GRAD-PS 0.399 vs GRAD-SR 0.752 at r=4800 | Helped |
| gradient-based sampling vs uniform sampling on synthetic mixture Gaussian data | least-squares subsampling · GA, MG1, MG2 synthetic (n up to 500K) | log MSE | Helped |
| gradient-based sampling vs leverage-based sampling on Gaussian synthetic data | least-squares subsampling · GA synthetic | log MSE | Helped |
| gradient-based sampling computed in O(nd) instead of leverage scores | probability computation cost · n=500K synthetic timing | user time (s) | Helped |
| gradient-based sampling vs leverage-based sampling in MSE on CASP with sampling with replacement | least-squares subsampling · CASP real data (SR) | MSE: GRAD-SR 1.567e-07 vs LEV-SR 2.050e-07 at r=4500 but GRAD-SR 2.069e-05 vs LEV-SR 1.962e-05 at r=45 | Mixed |
| gradient-based sampling vs leverage on CASP with Poisson sampling at small r | least-squares subsampling · CASP real data (PS) | MSE: GRAD-PS 2.411e-05 vs LEV-PS 2.118e-05 at r=45; GRAD-PS 1.179e-07 vs LEV-PS 1.694e-07 at r=4500 | Mixed |
Closest papers by meaning
- Safe Adaptive Importance Sampling (NeurIPS 2017 · similarity 0.88)
- Robust Gradient-Based Markov Subsampling (AAAI 2020 · similarity 0.88)
- First-Order Adaptive Sample Size Methods to Reduce Complexity of Empirical Risk Minimization (NeurIPS 2017 · similarity 0.87)
- A Provably Accurate Randomized Sampling Algorithm for Logistic Regression (AAAI 2024 · similarity 0.85)
- One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently (NeurIPS 2024 · similarity 0.85)
- Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond (ICML 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.