• This event has passed.

# SILO Seminar Series: Sam Wang and Kwang-Sung Jun

## 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.

SILO is a lecture series with speakers from the UW faculty, graduate students or invited researchers that discuss mathematical related topics. The seminars are organized by WID’s Optimization research group.
SILO’s purpose is to provide a forum that helps connect and recruit mathematically-minded graduate students. SILO is a lunch-and-listen format, where speakers present interesting math topics while the audience eats lunch.

### Details

Date:
September 27, 2017
Time:
12:30 pm - 1:30 pm
Event Category:

### Venue

Orchard View Room
3rd Floor Orchard View Room, 330 N. Orchard St.