Learning-Augmented Moment Estimation on Time-Decay Models

• URL: http://arxiv.org/abs/2603.02488v1
• Date: Tue, 03 Mar 2026 00:42:34 GMT
• Title: Learning-Augmented Moment Estimation on Time-Decay Models
• Authors: Soham Nagawanshi, Shalini Panthangi, Chen Wang, David P. Woodruff, Samson Zhou,
• Abstract summary: We use an oracle for the heavy-hitters of datasets to give learning-augmented algorithms for a number of fundamental problems.<n>We complement our theoretical results with a number of empirical evaluations that demonstrate the practical efficiency of our algorithms on real and synthetic datasets.
• Score: 55.06256430461023
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Efficient Machine Unlearning via Influence Approximation [75.31015485113993]
  Influence-based unlearning has emerged as a prominent approach to estimate the impact of individual training samples on model parameters without retraining.<n>This paper establishes a theoretical link between memorizing (incremental learning) and forgetting (unlearning)<n>We introduce the Influence Approximation Unlearning algorithm for efficient machine unlearning from the incremental perspective.
  arXiv  Detail & Related papers  (2025-07-31T05:34:27Z)
• Efficient Causal Discovery for Autoregressive Time Series [0.0]
  Our algorithm significantly reduces computational complexity compared to existing methods, making it more efficient and scalable to larger problems.<n>We rigorously evaluate its performance on synthetic datasets, demonstrating that our algorithm not only outperforms current techniques, but also excels in scenarios with limited data availability.
  arXiv  Detail & Related papers  (2025-07-10T16:27:33Z)
• PILOT: A Pre-Trained Model-Based Continual Learning Toolbox [65.57123249246358]
  This paper introduces a pre-trained model-based continual learning toolbox known as PILOT.<n>On the one hand, PILOT implements some state-of-the-art class-incremental learning algorithms based on pre-trained models, such as L2P, DualPrompt, and CODA-Prompt.<n>On the other hand, PILOT fits typical class-incremental learning algorithms within the context of pre-trained models to evaluate their effectiveness.
  arXiv  Detail & Related papers  (2023-09-13T17:55:11Z)
• LAVA: Data Valuation without Pre-Specified Learning Algorithms [20.578106028270607]
  We introduce a new framework that can value training data in a way that is oblivious to the downstream learning algorithm. We develop a proxy for the validation performance associated with a training set based on a non-conventional class-wise Wasserstein distance between training and validation sets. We show that the distance characterizes the upper bound of the validation performance for any given model under certain Lipschitz conditions.
  arXiv  Detail & Related papers  (2023-04-28T19:05:16Z)
• Model-based Offline Imitation Learning with Non-expert Data [7.615595533111191]
  We propose a scalable model-based offline imitation learning algorithmic framework that leverages datasets collected by both suboptimal and optimal policies. We show that the proposed method textitalways outperforms Behavioral Cloning in the low data regime on simulated continuous control domains.
  arXiv  Detail & Related papers  (2022-06-11T13:08:08Z)
• Using Time-Series Privileged Information for Provably Efficient Learning of Prediction Models [6.7015527471908625]
  We study prediction of future outcomes with supervised models that use privileged information during learning. privileged information comprises samples of time series observed between the baseline time of prediction and the future outcome. We show that our approach is generally preferable to classical learning, particularly when data is scarce.
  arXiv  Detail & Related papers  (2021-10-28T10:07:29Z)
• Learnability of Learning Performance and Its Application to Data Valuation [11.78594243870616]
  In most machine learning (ML) tasks, evaluating learning performance on a given dataset requires intensive computation. The ability to efficiently estimate learning performance may benefit a wide spectrum of applications, such as active learning, data quality management, and data valuation. Recent empirical studies show that for many common ML models, one can accurately learn a parametric model that predicts learning performance for any given input datasets using a small amount of samples.
  arXiv  Detail & Related papers  (2021-07-13T18:56:04Z)
• Low-Regret Active learning [64.36270166907788]
  We develop an online learning algorithm for identifying unlabeled data points that are most informative for training. At the core of our work is an efficient algorithm for sleeping experts that is tailored to achieve low regret on predictable (easy) instances.
  arXiv  Detail & Related papers  (2021-04-06T22:53:45Z)
• DEALIO: Data-Efficient Adversarial Learning for Imitation from Observation [57.358212277226315]
  In imitation learning from observation IfO, a learning agent seeks to imitate a demonstrating agent using only observations of the demonstrated behavior without access to the control signals generated by the demonstrator. Recent methods based on adversarial imitation learning have led to state-of-the-art performance on IfO problems, but they typically suffer from high sample complexity due to a reliance on data-inefficient, model-free reinforcement learning algorithms. This issue makes them impractical to deploy in real-world settings, where gathering samples can incur high costs in terms of time, energy, and risk. We propose a more data-efficient IfO algorithm
  arXiv  Detail & Related papers  (2021-03-31T23:46:32Z)
• A Constraint-Based Algorithm for the Structural Learning of Continuous-Time Bayesian Networks [70.88503833248159]
  We propose the first constraint-based algorithm for learning the structure of continuous-time Bayesian networks. We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence.
  arXiv  Detail & Related papers  (2020-07-07T07:34:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.