Agnostic Continuous-Time Online Learning

We study agnostic online learning from continuous-time data streams, a setting that naturally arises in applications such as environmental monitoring, personalized recommendation, and high-frequency trading. Unlike classical discrete-time models, learners in this setting must interact with a continually evolving data stream while making queries and updating models only at sparse, strategically selected times. We develop a general theoretical framework for learning from both oblivious and adaptive data streams, which may be noisy and non-stationary. For oblivious streams, we present a black-box reduction to classical online learning that yields a regret bound of T • R(S)/S for any class with discrete-time regret R(S), where T is the time horizon and S is the query budget. For adaptive streams, which can evolve in response to learner actions, we design a dynamic query strategy in conjunction with a novel importance weighting scheme that enables unbiased loss estimation. In particular, for hypothesis class H with a finite Littlestone dimension, we establish a tight regret bound of Θ(T • Ldim(H)/S) that holds in both settings. Our results provide the first quantitative characterization of agnostic learning in continuous-time online environments with limited interaction.