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
Fp Frequency ( p⩾2 )
O~(n1/2−1/p/ε4)
Streaming
[ JLL+20 ]
Ω(n1/2−1/p/ε2/p)
Any
Lower bound, [ JLL+20 ]
not specified
Sliding Window
[ SSM24 ]
O~(n1/2−1/p⋅p1+p/ε4+p)
General Time-decay (e.g., Sliding Window)
This work, Theorem 1
Rectangle Fp Frequency
O~(Δd(1/2−1/p)⋅\poly(εd,d))
Streaming
[ JLL+20 ]
O~(Δd(1/2−1/p)⋅\poly(εppp,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.
Fig. 1 : Example of smooth histogram framework. Here ALG(t2) and ALG(t3) sandwich the active elements and are thus good approximations of the sliding window.
Fig. 2 : Experiments for ℓ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) .
Fig. 3 : Experiments for ℓ3 estimation on CAIDA using multiple oracles
Fig. 4 : Experiments for ℓ3 estimation on AOL
Fig. 5 : Experiments for ℓ3 estimation on synthetic data
Fig. 6 : Experiments for (k,p) -cascaded norm estimation on synthetic data
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.
Vladimir Braverman, Chen Wang, Liudeng Wang +1
Johns Hopkins University · Rensselaer Polytechnic Institute · Texas A&M University
The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introduce a novel model for learning-augmented algorithms inspired by online learning. In this model, we are given a sequence of instances of a problem and the goal of the learning-augmented algorithm is to use prior instances to propose a solution to a future instance of the problem. The performance of the algorithm is measured by its average performance across all the instances, where the performance on a single instance is the ratio between the cost of the algorithm's solution and that of an optimal solution for that instance. We apply this framework to the classic k-median clustering problem, and give an efficient learning algorithm that can approximately match the average performance of the best fixed k-median solution in hindsight across all the instances. We also experimentally evaluate our algorithm and show that its empirical performance is close to optimal, and also that it automatically adapts the solution to a dynamically changing sequence.
Classical optimization theory largely focuses on fixed objective functions, whereas many modern learning systems operate in dynamic environments where data arrive sequentially and decisions must be updated continuously. In this work, we study optimization with streaming data over a distributed network of agents. We adopt a structured, weight-based formulation that explicitly captures the streaming-data origin of the time-varying objective: at each time step, every agent receives a new sample, and the network seeks to track the minimizer of a temporally weighted objective formed from all samples observed across the network so far. We focus on decentralized gradient descent (DGD) with a limited communication/computation budget, where at each time step, only a limited number of DGD iterations can be performed before the objective changes again. For strongly convex and smooth losses, we analyze the tracking error with respect to the time-varying minimizer through a fixed-point theory lens. Our analysis reveals that the tracking error decomposes into a fixed-point tracking term and a bias term induced by data heterogeneity across agents. We specialize the analysis to two natural weighting strategies: uniform weights, which treat all samples equally, and exponentially discounted weights, which geometrically decay the influence of older data. Under uniform weighting, DGD tracks the fixed-point at a rate O(1/t), whereas discounted weighting yields a non-vanishing fixed-point tracking floor controlled by the discount factor. In both cases, decentralization induces an additional non-zero bias floor under a constant step size. We validate our theoretical findings through numerical simulations.
Muhammad Faraz Ul Abrar, Nicolò Michelusi, Erik G. Larsson
School of Electrical, Computer and Energy Engineering, Arizona State University · Department of Electrical Engineering (ISY), Linköping University