Research map / Learning theory and algorithms / Sample complexity
Learning-Augmented Frequent Directions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends learning-augmented frequency estimation to matrix streaming by proposing a learned Frequent Directions algorithm (and a deterministic learned Misra-Gries), with Zipfian-based error bounds and experiments on video/hyperspectral and network/search streams.
Problem
Learning-augmented streaming for frequency estimation and its high-dimensional matrix analogue, where rows of a matrix arrive in a stream and the goal is to recover important (top singular) directions in small space using predictions of frequent directions.
Approach
Reserve part of the sketch for predicted frequent directions (exact tracking of projections onto predicted orthonormal directions) and run standard Frequent Directions on the orthogonal residual; for basis-vector inputs this reduces to a learned deterministic Misra-Gries that matches the best randomized learned bounds without Zipf-specific tuning.
Key results
- For matrix streaming, learning-augmented Frequent Directions improves over base Frequent Directions by 1-2 orders of magnitude on all four video/hyperspectral datasets.
- Learned Misra-Gries achieves expected error Theta(n/(m (ln d)^2)) under Zipfian frequencies with a perfect oracle, matching learned CountSketch++ bounds without randomness.
- On CAIDA and AOL frequency estimation, learned Misra-Gries improves significantly over learned CountSketch and is competitive with learned CountSketch++.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use learned predictions of frequent directions | Frequent Direction · Matrix streaming, Zipfian singular values | weighted error | Helped |
| Use learned predictions of frequent elements | Misra-Gries · Frequency estimation, Zipfian frequencies | weighted error | Helped |
| Use learned predictions of frequent directions | Frequent Direction · Hyper, Logo, Friends, and Eagle datasets | median error: 1-2 orders of magnitude | Helped |
| Use learned predictions of frequent elements | Misra-Gries · CAIDA and AOL | median weighted error | Helped |
| Use learned predictions of frequent elements | Misra-Gries · CAIDA and AOL | median weighted error | Mixed |
| Increase sketch rank (equivalently, space) | Learned Frequent Direction and Frequent Direction · Hyper, Logo, Friends, and Eagle datasets | error | Helped |
Limitations
- Learned Frequent Directions lacks a robustness guarantee; adversarial predictions can make error much worse than classic FD without a residual-error check.
- Theoretical bounds assume a perfect oracle or predictions accurate on top elements; the analysis is for Zipfian-distributed data.
Experimental setup
Datasets: CAIDA AOL Hyper Logo Friends Eagle
Benchmarks: CAIDA AOL Hyper Logo Friends Eagle
Metrics: weighted error median error across streams
Baselines: Frequent Directions learned CountSketch learned CountSketch++ exact truncated SVD
Builds on: Frequent Directions Misra-Gries Hsu et al. learning-based frequency estimation
Closest papers by meaning
- The Heavy Hitter Oracle: Enhancing Frequency Estimation in Skewed Data Streams (NeurIPS 2026 · similarity 0.92)
- Learning-Based Frequency Estimation Algorithms (ICLR 2019 · similarity 0.91)
- Improved Frequency Estimation Algorithms with and without Predictions (NeurIPS 2023 · similarity 0.91)
- MaxSketch: Robust Distinct Counting in Streams via Random Projections (NeurIPS 2026 · similarity 0.85)
- Learning-Augmented Streaming Algorithms for Correlation Clustering (NeurIPS 2025 · similarity 0.84)
- Towards Combating Frequency Simplicity-biased Learning for Domain Generalization (NeurIPS 2024 · similarity 0.82)
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.