Causal discovery with high dimensional non-Gaussian data & Scalable Generalized Linear Bandits: Online Computation and Hashing

In this talk, we will consider linear structural equation models which correspond to directed acyclic graphs (DAGs). These models assume that each observed variable is a linear function of the other variables and some error term. It has been previously shown for DAGs, when the error terms in a SEM are non-Gaussian, the exact causal structure–not simply the Markov equivalence class–can be identified from observational data. We show that for suitably sparse graphs, when the error terms follow a log-concave distribution (but are non-Gaussian), the graph can also be identified in the high dimensional setting where the number of variables may exceed the number of observations.

&

Generalized Linear Bandits (GLBs), a natural extension of the stochastic linear bandits, has been popular and successful in recent years. However, existing GLBs scale poorly with the number of rounds and the number of arms, limiting their utility in practice. We propose new, scalable solutions to the GLB problem in two respects. First, unlike existing GLBs, whose per-time-step space and time complexity grow at least linearly with time $t$, we propose a new algorithm that performs online computations to enjoy a constant space and time complexity. At its heart is a novel Generalized Linear extension of the Online-to-confidence-set Conversion (GLOC method) that takes \emph{any} online learning algorithm and turns it into a GLB algorithm. As a special case, we apply GLOC to the online Newton step algorithm, which results in a low-regret GLB algorithm with much lower time and memory complexity than prior work. Second, for the case where the number $N$ of arms is very large, we propose new algorithms in which each next arm can be selected via hashing, which provides a sublinear time complexity in $N$. Our algorithm which achieves the best regret bound among “hash-amenable” bandit algorithms. We conclude the talk with preliminary experimental results confirming the merits of our methods.

Video: https://vimeo.com/236645957