用机器学习辅助估计时间衰减数据中的矩，提升空间效率。
Learning-Augmented Moment Estimation on Time-Decay Models
- 用机器学习预测数据重要性，指导稀疏采样
- 在真实与合成数据上实现更优的内存占用
- 适合处理有隐私限制的旧数据过期场景
受机器学习广泛应用的启发，近期研究探索了流式计算中学习增强型算法。这些工作表明，当使用机器学习模型实现自然且实用的预言机时，可获得比传统方法更高效的空间利用率，而后者在理论上无法实现。然而，当数据权重不均时，例如在滑动窗口模型中需清除旧数据（如受隐私法规约束），我们对这类问题的理解仍十分有限。本文利用重项检测预言机，为时间衰减设置下的若干基础问题设计学习增强型算法，包括范数/矩估计、频率估计、级联范数和矩形矩估计。通过一系列实证评估，展示了算法在真实与合成数据集上的实际效率优势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。