Research map / Learning theory and algorithms / Prediction and decision losses
Putting the “Learning" into Learning-Augmented Algorithms for Frequency Estimation
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 |
|---|---|---|---|
| Train predictor with BatchRank loss (sub-batch normalized, K=8) instead of unweighted log loss | learned count-min sketch predictor (LSTM) · CAIDA minute 60 | average absolute frequency error ratio vs Hsu et al. loss: Hsu et al. error averages 121% of BatchRank error | Helped |
| Train predictor with BatchRank loss instead of unweighted log loss | learned Count-Sketch predictor · CAIDA minute 60 | average absolute frequency error ratio vs Hsu et al. loss: ratio reaching over 160% | Helped |
| Use BatchRank loss instead of unweighted log loss | predictor coverage · CAIDA minute 60, top 10% keys | coverage (%): 55.7% to 62.8% | Helped |
| Use L1 loss (directly predicting frequency) instead of log-based or BatchRank losses (ablation) | predictor coverage · CAIDA minute 60 | coverage (%): unweighted L1 35.5% vs unweighted log 55.7% at 10% | Hurt |
| Use weighted log loss (F1-weighted) instead of unweighted log loss (ablation) | predictor coverage · CAIDA minute 60, top 1% keys | coverage (%): 28.3% vs 31.1% at 1%; 61.6% vs 55.7% at 10% | Mixed |
| Use one hash row instead of two in count-min sketch with screening (ablation) | count-min sketch with perfect screening (synthetic Zipf) · synthetic, 20000 cells, perfect screening | average absolute frequency error: 62.75 vs 109.17 | Helped |
| Use one hash row instead of two in count-min sketch without screening (ablation) | count-min sketch with no screening (synthetic Zipf) · synthetic, 20000 cells, no screening | average absolute frequency error: 592.16 vs 529.23 | Hurt |
| Use one hash row instead of two in count-min sketch with imperfect screening (ablation) | count-min sketch with imperfect screening (synthetic Zipf) · synthetic, 20000 cells, imperfect screening | average absolute frequency error: 129.55 vs 164.18 | Helped |
Closest papers by meaning
- Learning-Augmented Frequent Directions (ICLR 2025 · similarity 0.90)
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.82)
- Learning-Augmented Algorithms with Explicit Predictors (NeurIPS 2024 · similarity 0.81)
- Sample-Optimal Agnostic Boosting with Unlabeled Data (ICML 2025 · similarity 0.81)
- Towards Combating Frequency Simplicity-biased Learning for Domain Generalization (NeurIPS 2024 · similarity 0.81)
- Uncertainty Herding: One Active Learning Method for All Label Budgets (ICLR 2025 · similarity 0.80)
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.