Research map / Learning theory and algorithms / Sample complexity
Asymptotic Analysis of Sampling Estimators for Randomized Numerical Linear Algebra Algorithms
Ping Ma, Yongkai Chen, Xinlian Zhang, Xin Xing, Jingyi Ma, Michael W. Mahoney
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 |
|---|---|---|---|
| use IC sampling probabilities instead of BLEV/SLEV for estimating beta_0 | RandNLA sampling estimator · Simulated MN and T3 data | variance of estimate | Improved |
| use IC, RL, PL instead of BLEV and SLEV on heavy-tailed T1 data | RandNLA sampling estimator · Simulated T1 data (sample size greater than 200) | variance of estimate | Improved |
| mix BLEV with uniform sampling (SLEV) | BLEV leverage sampling · Simulated data | variance of estimate | Improved |
| use ICNLEV, RLNLEV, PLNLEV instead of SLEV and BLEV for approximating OLS | RandNLA sampling estimator · Simulated LN and T1 data | variance of estimate | Improved |
| use ICNLEV instead of other samplers | RandNLA sampling estimator · Flight delay dataset (3,274,894 flights) | variance of beta_OLS approximation | Improved |
| use ICNLEV, RLNLEV, PLNLEV instead of SLEV and BLEV | RandNLA sampling estimator · YearPredictionMSD dataset (515,345 songs) | variance of beta_OLS approximation | Improved |
| use different sampling estimators | RandNLA sampling estimator · All simulation and real datasets | squared bias | No clear effect |
Closest papers by meaning
- Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton (ICML 2025 · similarity 0.88)
- Debiasing Random Oblique Projections for Subsampled OLS and Fast CUR in High Dimensions (NeurIPS 2026 · similarity 0.87)
- A Provably Accurate Randomized Sampling Algorithm for Logistic Regression (AAAI 2024 · similarity 0.86)
- Estimating the Permanent by Nesting Importance Sampling (ICML 2024 · similarity 0.85)
- Non-Asymptotic Analysis Of Data Augmentation For Precision Matrix Estimation (NeurIPS 2025 · similarity 0.85)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 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.
