Learning from Snapshots of Discrete and Continuous Data Streams
Authors: Pramith Devulapalli, Steve Hanneke
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we adopt a learning-theoretic perspective in understanding the fundamental nature of learning different classes of functions from both discrete data streams and continuous data streams. In our first framework, the update-and-deploy setting, a learning algorithm discretely queries from a process to update a predictor designed to make predictions given as input the data stream. We construct a uniform sampling algorithm that can learn with bounded error any concept class with finite Littlestone dimension. Our second framework, known as the blind-prediction setting, consists of a learning algorithm generating predictions independently of observing the process, only engaging with the process when it chooses to make queries. Interestingly, we show a stark contrast in learnability where non-trivial concept classes are unlearnable. However, we show that adaptive learning algorithms are necessary to learn sets of time-dependent and data-dependent functions, called pattern classes, in either framework. Finally, we develop a theory of pattern classes under discrete data streams for the blind-prediction setting. |
| Researcher Affiliation | Academia | Pramith Devulapalli Department of Computer Science Purdue University pdevulap@purdue.edu Steve Hanneke Department of Computer Science Purdue University steve.hanneke@gmail.com |
| Pseudocode | Yes | Algorithm 1 Uniform Sampler(H, ) Algorithm 2 Adaptive Sampler(P) Algorithm 3 BP-SOA(P, Q) |
| Open Source Code | No | Justification: This is a completely theoretical paper so there are no experiments. Guidelines: The answer NA means that paper does not include experiments requiring code. ... Justification: This is a completely theoretical paper so we don t have any code, data, or models. |
| Open Datasets | No | Justification: This is a completely theoretical paper so there are no experiments. Guidelines: The answer NA means that the paper does not include experiments. ... Justification: This is a completely theoretical paper so we don t have any code, data, or models. |
| Dataset Splits | No | Justification: This is a completely theoretical paper so there are no experiments. Guidelines: The answer NA means that the paper does not include experiments. ... Justification: This is a completely theoretical paper so we don t have any code, data, or models. |
| Hardware Specification | No | Justification: This is a completely theoretical paper so there are no experiments. Guidelines: The answer NA means that the paper does not include experiments. ... Justification: This is a completely theoretical paper so there are no experiments. |
| Software Dependencies | No | Justification: This is a completely theoretical paper so there are no experiments. Guidelines: The answer NA means that the paper does not include experiments requiring code. ... Justification: This is a completely theoretical paper so there are no experiments. |
| Experiment Setup | No | Justification: This is a completely theoretical paper so there are no experiments. Guidelines: The answer NA means that the paper does not include experiments. |