The Taub Faculty of Computer Science Events and Talks

We consider online prediction problems of combinatorial concepts. Examples of such concepts include s-t paths, permutations, truth assignments, set covers, and so on. The goal of the online prediction algorithm is to compete with the best fixed combinatorial concept in hindsight. A generic approach to this problem is to design an online prediction algorithm using the corresponding offline (approximation) algorithm as an oracle. The current state-of-the art method, however, is not efficient enough. In this talk, we propose a more efficient online prediction algorithm when the offline approximation algorithm has a guarantee of the integrality gap.

Short bio:
Kohei obtained a Ph.D at Tokyo Institute of Technology in 2005. He then joined Kyushu University in Japan, where he is now an assistant professor at the Department of Informatics. His research focuses on theoretical aspects of machine learning, e.g., boosting, optimization and online learning. Currently, he is a member of the ELC project (Exploring the Limits of Computation, http://www.al.ics.saitama-u.ac.jp/elc/en/), a large research project on computational complexity funded by Japanese government.