Research map / Learning theory and algorithms / Sample complexity
Sampling Sketches for Concave Sublinear Functions of Frequencies
Edith Cohen, Ofir Geri
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 the proposed composable sampling sketch instead of aggregating keys before sampling | Weighted frequency estimation · Real and synthetic datasets; ν^0.5 and ln(1+ν) | NRMSE | Mixed |
| Increase sample size k from 25 to 100 | Sampling sketch · abcnews, f(ν)=ν^0.5 | NRMSE: 0.213 -> 0.105 | Improved |
| Increase sample size k from 25 to 100 | Sampling sketch · flickr, f(ν)=ln(1+ν) | NRMSE: 0.227 -> 0.097 | Improved |
| Use the sketch rather than aggregated PPSWOR | Frequency estimation · abcnews, f(ν)=ln(1+ν), k=100 | NRMSE: 0.115 -> 0.102 | Improved |
| Use the sketch rather than aggregated PPSWOR | Frequency estimation · flickr, f(ν)=ν^0.5, k=100 | NRMSE: 0.095 -> 0.115 | Hurt |
| Use the sketch rather than priority sampling | Frequency estimation · zipf1.2, f(ν)=ν^0.5, k=100 | NRMSE: 0.096 -> 0.098 | Hurt |
| Use the sketch rather than aggregated priority sampling | Frequency estimation · abcnews, f(ν)=ln(1+ν), k=100 | NRMSE: 0.103 -> 0.102 | No clear effect |
| Use the adaptive split between low- and high-range contributions with stochastic PPSWOR sampling | Sampling sketch · Theorem-level estimator guarantee | Variance upper bound: 4/((1-ε)^2 (k-2)) times the corresponding frequency-weight product | Improved |
| Use a concave sublinear function to weight key frequencies instead of raw frequency | Frequency-weighted sampling · Applications with skewed frequencies | High-frequency key influence | Improved |
Closest papers by meaning
- Matrix Product Sketching via Coordinated Sampling (ICLR 2025 · similarity 0.84)
- Statistical-Computational Trade-offs for Density Estimation (NeurIPS 2024 · similarity 0.84)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.84)
- Simple and Optimal Sublinear Algorithms for Mean Estimation (NeurIPS 2025 · similarity 0.84)
- Sampling Binary Data by Denoising through Score Functions (ICML 2025 · similarity 0.84)
- A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers (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.
