Learning-Augmented Moment Estimation on Time-Decay Models

Soham Nagawanshi; Shalini Panthangi; Chen Wang; David P. Woodruff; Samson Zhou

cs.DSMar 3, 2026

Learning-Augmented Moment Estimation on Time-Decay Models

Authors: Soham Nagawanshi, Shalini Panthangi, Chen Wang, David P. Woodruff, Samson Zhou

Organizations: Texas A&M University · Carnegie Mellon University · Rensselaer Polytechnic Institute

Abstract

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.

Figures & tables

Task	Space Bound	Model	Remark
$F_{p}$ Frequency ( $p\geqslant 2$ )	$\tilde{O}(n^{1/2-1/p}/\varepsilon^{4})$	Streaming	[ JLL+20 ]
	$\Omega(n^{1/2-1/p}/\varepsilon^{2/p})$	Any	Lower bound, [ JLL+20 ]
	not specified	Sliding Window	[ SSM24 ]
	$\tilde{O}(n^{1/2-1/p}\cdot p^{1+p}/\varepsilon^{4+p})$	General Time-decay (e.g., Sliding Window)	This work, Theorem 1
Rectangle $F_{p}$ Frequency	$\tilde{O}(\Delta^{d(1/2-1/p)}\cdot\poly(\frac{d}{\varepsilon},d))$	Streaming	[ JLL+20 ]
Rectangle $F_{p}$ Frequency	$\tilde{O}(\Delta^{d(1/2-1/p)}\cdot\poly(\frac{p^{p}}{\varepsilon^{p}},d))$	General Time-decay (e.g., Sliding Window)	This work, Theorem 3

Table 1: Summary of the results and their comparisons with existing work. The theorem pointers are directed to the sliding-window algorithms as an illustration.

Panel of Figure 2 — Fig. 1 : Example of smooth histogram framework. Here $\textnormal{{ALG}}^{(t_{2})}$ and $\textnormal{{ALG}}^{(t_{3})}$ sandwich the active elements and are thus good approximations of the sliding window.

Panel of Figure 3 — Fig. 2 : Experiments for $\ell_{2}$ norm estimation on CAIDA. Note on the notation: the variable $n$ in figures refers to stream length (which is $m$ at other places of the paper) .

Panel of Figure 4 — Fig. 3 : Experiments for $\ell_{3}$ estimation on CAIDA using multiple oracles

Panel of Figure 5 — Fig. 4 : Experiments for $\ell_{3}$ estimation on AOL

Panel of Figure 6 — Fig. 5 : Experiments for $\ell_{3}$ estimation on synthetic data

Panel of Figure 7 — Fig. 6 : Experiments for $(k,p)$ -cascaded norm estimation on synthetic data

Learning-Augmented Algorithms

Learning-augmented algorithms use predictions to improve algorithmic performance while retaining guarantees when predictions are wrong.

See all 54 papers

Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits
Jun 8, 2026Vladimir Braverman, Chen Wang, Liudeng Wang +1Multi-Armed Bandits Best-Arm Identification
Johns Hopkins University · Rensselaer Polytechnic Institute · Texas A&M University
Learning-Augmented Algorithms for $k$ -median via Online Learning
Mar 18, 2026Anish Hebbar, Rong Ge, Amit Kumar +1Learning-Augmented Algorithms Clustering
Duke University · IIT Delhi
Decentralized Time-Varying Optimization for Streaming Data via Temporal Weighting
May 7, 2026Muhammad Faraz Ul Abrar, Nicolò Michelusi, Erik G. LarssonDecentralized Optimization
School of Electrical, Computer and Energy Engineering, Arizona State University · Department of Electrical Engineering (ISY), Linköping University

Jun 8, 2026J/K move · Enter open · S save

Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits

Vladimir Braverman, Chen Wang, Liudeng Wang, Samson Zhou

Johns Hopkins University · Rensselaer Polytechnic Institute · Texas A&M University

Multi-Armed Bandits Best-Arm Identification Streaming Algorithms Bandit Learning

Open paper AskPDF arXiv

Motivated by the recency effect in online learning, we study algorithms for single-pass sliding-window streaming multi-armed bandits (MABs) in this paper. In this setting, we are given

n

arms with unknown sub-Gaussian reward distributions and a parameter

W

. The arms arrive in a single-pass stream, and only the most recent

W

arms are considered valid. The algorithm is required to perform pure exploration and regret minimization with limited memory, defined as the number of stored arms. The model is a natural extension of the streaming multi-armed bandits model (without the sliding window) that has been extensively studied in recent years. We provide a comprehensive analysis of both the pure exploration and regret minimization problems with the model. For pure exploration, we prove that finding the best arm is hard with sublinear memory while finding an approximate best arm admits an efficient algorithm. For regret minimization, we explore a new notion of regret and give sharp memory-regret trade-offs for any single-pass algorithm. We complement our theoretical results with experiments, demonstrating the trade-offs between sample, regret, and memory.

Abstract

Learning-Augmented Algorithms

Explore similar work

Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits

Learning-Augmented Algorithms for kkk-median via Online Learning

Decentralized Time-Varying Optimization for Streaming Data via Temporal Weighting

Learning-Augmented Algorithms for $k$ -median via Online Learning