Research map / Learning theory and algorithms / Sample complexity
Learning-based Support Estimation in Sublinear Time
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 |
|---|---|---|---|
| Use frequency predictions to partition elements into probability intervals and estimate support within each interval | Support estimation on AOL · AOL, sample size 5%·n | relative error: 2.2-fold | Helped |
| Use frequency predictions to partition elements into probability intervals and estimate support within each interval | Support estimation on AOL · AOL, sample size 10%·n | relative error: 3.0-fold | Helped |
| Use frequency predictions to partition elements into probability intervals and estimate support within each interval | Support estimation on IP · IP, sample size 1%·n | relative error: 1.7-fold | Helped |
| Use frequency predictions to partition elements into probability intervals and estimate support within each interval | Support estimation on IP · IP, sample size 2.5%·n | relative error: 3.0-fold | Helped |
| Use the Canonne-Rubinfeld estimator with an imperfect predictor instead of the learning-based estimator | Support estimation · AOL | relative error | Helped |
| Use the Canonne-Rubinfeld estimator with an imperfect predictor instead of the learning-based estimator | Support estimation · IP and Zipfian | relative error | Hurt |
| Choose a very small base for the probability intervals (ablation) | Learning-based support estimation · AOL, IP, and Zipfian | relative error | Hurt |
| Increase the interval base until one interval dominates, reducing use of predictor information (ablation) | Learning-based support estimation · AOL, IP, and Zipfian | relative error | Hurt |
| Use the estimator’s polynomial correction for high-probability intervals instead of counting sampled distinct elements (ablation) | Learning-based support estimation · Support estimation | estimation performance | Hurt |
Closest papers by meaning
- Learning-Augmented Frequent Directions (ICLR 2025 · similarity 0.85)
- Prediction-Augmented Trees for Reliable Statistical Inference (NeurIPS 2026 · similarity 0.85)
- Towards a statistical theory of data selection under weak supervision (ICLR 2024 · similarity 0.84)
- Optimal Hypothesis Selection in (Almost) Linear Time (NeurIPS 2024 · similarity 0.84)
- Estimating Unknown Population Sizes Using the Hypergeometric Distribution (ICML 2024 · similarity 0.84)
- Statistical-Computational Trade-offs for Density Estimation (NeurIPS 2024 · similarity 0.83)
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.