# Learning-Augmented Moment Estimation on Time-Decay Models

arXiv: https://arxiv.org/abs/2603.02488 · HTML: https://mlsanity.com/paper/2603.02488/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 69 references that are in the map.
- First posted on arXiv 3 Mar 2026.

## Builds on (most cited first, 30 of 30)

- [TrafficStream: A Streaming Traffic Flow Forecasting Framework Based on Graph Neural Networks and Continual Learning](https://mlsanity.com/paper/2106.06273/) (2021)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [Learning Augmented Binary Search Trees](https://mlsanity.com/paper/2206.12110/) (2022)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Near Optimal Linear Algebra in the Online and Sliding Window Models](https://mlsanity.com/paper/1805.03765/) (2018)
- [Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators](https://mlsanity.com/paper/2011.07471/) (2020)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Learning-Augmented Streaming Algorithms for Approximating MAX-CUT](https://mlsanity.com/paper/2412.09773/) (2024)
- [Sliding Window Algorithms for k-Clustering Problems](https://mlsanity.com/paper/2006.05850/) (2020)
- [Learning-Augmented Hierarchical Clustering](https://mlsanity.com/paper/2506.05495/) (2025)
- [Improved Algorithms for Time Decay Streams](https://mlsanity.com/paper/1907.07574/) (2019)
- [Truly Perfect Samplers for Data Streams and Sliding Windows](https://mlsanity.com/paper/2108.12017/) (2021)
- [Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches](https://mlsanity.com/paper/2110.15533/) (2021)
- [Near-Optimal k-Clustering in the Sliding Window Model](https://mlsanity.com/paper/2311.00642/) (2023)
- [Learning-Augmented Search Data Structures](https://mlsanity.com/paper/2402.10457/) (2024)
- [Fair Clustering in the Sliding Window Model](https://mlsanity.com/paper/2503.05173/) (2025)
- [Online Learning with Limited Information in the Sliding Window Model](https://mlsanity.com/paper/2601.03533/) (2026)
- [Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows](https://mlsanity.com/paper/1805.00212/) (2018)
- [Symmetric Norm Estimation and Regression on Sliding Windows](https://mlsanity.com/paper/2109.01635/) (2021)
- [Differentially Private L2-Heavy Hitters in the Sliding Window Model](https://mlsanity.com/paper/2302.11081/) (2023)
- [A New Information Complexity Measure for Multi-pass Streaming with Applications](https://mlsanity.com/paper/2403.20283/) (2024)
- [Learning-Augmented Frequency Estimation in Sliding Windows](https://mlsanity.com/paper/2409.11516/) (2024)
- [Learning-Augmented Frequent Directions](https://mlsanity.com/paper/2503.00937/) (2025)
- [Revisiting Frequency Moment Estimation in Random Order Streams](https://mlsanity.com/paper/1803.02270/) (2018)
- [Distributed mining of time--faded heavy hitters](https://mlsanity.com/paper/1812.01450/) (2018)
- [Separations for Estimating Large Frequency Moments on Data Streams](https://mlsanity.com/paper/2105.03773/) (2021)
- [Frequency Estimation with One-Sided Error](https://mlsanity.com/paper/2111.03953/) (2021)

## Built on by (most cited first, 2 of 2)

- [Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits](https://mlsanity.com/paper/2606.08977/) (2026)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)

## Abstract (arXiv)

Motivated by the prevalence and success of machine learning, a line of recent work has studied learning-augmented algorithms in the streaming model. These results have shown that for natural and practical oracles implemented with machine learning models, we can obtain streaming algorithms with improved space efficiency that are otherwise provably impossible. On the other hand, our understanding is much more limited when items are weighted unequally, for example, in the sliding-window model, where older data must be expunged from the dataset, e.g., by privacy regulation laws. In this paper, we utilize an oracle for the heavy-hitters of datasets to give learning-augmented algorithms for a number of fundamental problems, such as norm/moment estimation, frequency estimation, cascaded norms, and rectangular moment estimation, in the time-decay setting. We complement our theoretical results with a number of empirical evaluations that demonstrate the practical efficiency of our algorithms on real and synthetic datasets.