Online experiment design with causal structures
Creators: name: Sen, Rajat
name: 0000-0003-4677-643X
Publisher: name: The University of Texas at Austin
Year: 2019
Subjects: Online learning
Multi-armed bandits
Contextual bandits
Hyper-parameter tuning
Tree-search
CI testing

description: Modern learning systems like recommendation engines, computational advertising systems, online parameter tuning services are inherently online; i.e. these systems need to continually collect data, take decisions to optimize a certain objective and then collect more data with the objective of improving their predictive abilities. This leads to the well-known exploration (searching the space of possible decisions) and exploitation (choosing the optimal decision according to the learned model) dilemma. A principled way to capture this trade-off is the study of multi-armed bandit problems. On the other hand, these online learning systems are made up of several interacting components. Therefore, it is beneficial to study the pattern of interaction among these components, in order to explore in a sample efficient manner, which in turn leads to better exploitation. In this thesis, we will see that it is sometimes beneficial to view these online learning systems under the lens of causality; thus formalizing the pattern of interaction among the various components of the system, through causal graphical models. In our first problem, we study the contextual bandit problem with L observed contexts and K arms, with a latent low dimensional causal structure. We show that leveraging this latent low dimensional structure can lead to superior regret guarantees that are practical even for smaller time horizons. This also leads to the first regret guarantees for low-rank matrix completion where the rank is greater than one. Our second problem deals with leveraging information leakage in an online fashion in the presence of causal structures. We identify that in presence of general causal structures there is information leakage between different interventions viewed as arms of a bandit i.e. collecting data under one intervention can inform us about the statistics under other interventions. We demonstrate how to leverage this information leakage through adaptive importance sampling and apply our algorithm in biological networks and for interpretability of deep networks. This directly leads us to our third problem, where we use the idea of information leakage (explored in our second problem) in the context of stochastic contextual bandits. We propose the contextual bandits with stochastic experts problem and provide the first problem dependent regret bound in contextual bandits, where the scaling of the regret bound can potentially be as low as logarithmic in the number of experts. We show that our algorithm outperforms several state of the art algorithms on progressive validation tasks on multi-class classification data-sets. In our fourth problem, we look at conditional independence testing, which is one of the fundamental tools in causal structure learning. We reduce this problem into binary classification, through a nearest neighbor based bootstrap procedure. This enables us to use powerful supervised learning tools like gradient boosted trees or deep neural networks, that have desirable properties in higher dimensions. Finally in our last two chapters, we explore the application of online learning techniques in the context of hyper-parameter tuning, which is of growing importance in general machine learning, as modern neural networks have several tunable parameters and even training one such parameter configuration can take several hours to days. In our sixth problem, we cast hyper-parameter tuning as optimizing a multi-fidelity black-box function (which is noise-less) and propose a multi-fidelity tree search algorithm for the same. In the seventh problem we extend our model and algorithm, so that they can function even in the presence of noise. We show that our tree-search based algorithms can outperform state of the art hyper-parameter tuning algorithms on several benchmark data-sets