Research map / Learning theory and algorithms / Prediction and decision losses
Learning from Snapshots of Discrete and Continuous Data Streams
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies learnability of concept and pattern classes from continuous and discrete data streams via snapshot queries in two settings (update-and-deploy and blind-prediction), showing Littlestone dimension characterizes update-and-deploy learnability, non-trivial classes are unlearnable under blind prediction, and proposing a query-learning-distance theory for discrete pattern classes.
Problem
How to learn functions online from continuous-time data streams when the learner only observes snapshots at chosen times, and what combinatorial dimensions characterize learnability in the update-and-deploy and blind-prediction settings.
Approach
Formalizes learning from snapshots of continuous streams with two query-based settings; shows a randomized uniform-timestamp sampler (using SOA predictor) achieves finite expected error bounded by Delta*LD(H) under update-and-deploy, while under blind prediction non-trivial concept classes are unlearnable and adaptive samplers are needed for pattern classes; defines query-learning distance (QLD) f
Key results
- Uniform sampler A_unif achieves expected mistake bound at most Delta*LD(H) with linear querying when LD(H) is finite.
- Under blind-prediction, any concept class containing a classifier labeling two points differently has infinite mistake bound for every linear-query algorithm.
- An adaptive sampler achieves zero expected error on a constructed continuous pattern class where any random sampler has infinite mistake bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use uniform random query timestamps over intervals of width Δ and deploy SOA | Update-and-deploy learning of concept classes with finite Littlestone dimension · Continuous streams | expected mistake-bound: ≤ Δ LD(H) | Helped |
| apply any linear-querying learner to a concept class with infinite Littlestone dimension | Update-and-deploy learning · Continuous streams; LD(H) = ∞ | expected mistake-bound: = ∞ | Hurt |
| use blind-prediction instead of update-and-deploy for a non-trivial concept class | Learning concept classes with a classifier that labels two points differently · Continuous streams | expected mistake-bound: = ∞ | Hurt |
| use random sampling rather than adaptive sampling | Learning the constructed continuous pattern class P · Continuous pattern class P; update-and-deploy | expected mistake-bound: = ∞ | Hurt |
| adaptively query at timestamps when future stream information is revealed | Learning the constructed continuous pattern class P · Continuous pattern class P; blind-prediction | expected mistake-bound: = 0 | Helped |
| characterize deterministic realizable learning with Q queries using query-learning distance QLD | Learning discrete pattern classes in blind-prediction · Discrete pattern classes; query budget Q | optimal mistake-bound: M_Q(\mathcal{P}) = QLD(\mathcal{P}, Q) | Helped |
Surprising findings
- Non-trivial concept classes are unlearnable in the blind-prediction setting regardless of Littlestone dimension.
Limitations
- Results restricted to linear querying strategies O(t)
- Discrete pattern class theory restricted to realizable, binary labels and deterministic learners
- Update-and-deploy characterization for pattern classes left open
Experimental setup
Metrics: expected mistake bound
Builds on: Littlestone dimension Standard Optimal Algorithm self-directed online learning partial monitoring
Closest papers by meaning
- Learning from One Continuous Video Stream (CVPR 2024 · similarity 0.86)
- Efficient Adaptive Data Acquisition via Pretrained Belief Representations (NeurIPS 2026 · similarity 0.84)
- Rapid Learning without Catastrophic Forgetting in the Morris Water Maze (ICML 2024 · similarity 0.84)
- MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound (NeurIPS 2026 · similarity 0.83)
- Debiased Offline Representation Learning for Fast Online Adaptation in Non-stationary Dynamics (ICML 2024 · similarity 0.83)
- Learning-Augmented Algorithms with Explicit Predictors (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.