The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group


with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

TBD & Scalable Generalized Linear Bandits: Online Computation and Hashing

Sam Wang & Kwang-Sung Jun , Graduate Student - University of Washington & Graduate Student - University of Wisconsin

Date and Time: Sep 27, 2017 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building




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.