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 · (cid:112) 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.