UC Santa Barbara

Making decisions in real-time by learning patterns in an online data-stream is an important problem in modern machine learning (ML). Applications that fall under this umbrella include domain adaptation, change-point detection, portfolio-optimization, optimally pricing airline tickets based on changing market features etc. The features of the environment where an ML model is deployed change from time to time. Designing decision-making algorithms that can quickly adapt to these environmental changes on-the-fly is a topic of great significance.

In this thesis, we will design and analyse information-theoretically optimal algorithms for online decision-making under non-stationarities. The presentation will also encompass the utilization of these algorithms across a wide spectrum of applications, spanning time series forecasting, dynamic pricing, non-parametric regression, LQR control and unsupervised domain adaptation.

A main challenge in the theoretical analysis of the algorithms is to exploit the curved geometry of loss functions while deriving fast dynamic regret rates. This is attained by connecting ideas from the domains of locally adaptive non-parametric regression and strongly adaptive online learning. These fields have been conventionally studied separately by researchers. In this thesis we provide new tools to bridge these two domains. A byproduct of this fusion are novel results that do not require observation models with stringent stochastic assumptions for non-parametric regression and online convex optimization. Further, the developed algorithms are highly adaptive and do not require prior knowledge about the degree of non-stationarity in the environment. Our hope is that this thesis will inspire new collaborations between researchers from the communities of online learning and non-parametric regression.