Event section image

Stochastic Optimization with Queries



Dr. Takanori Maehara

Dr. Takanori Maehara

Unit Leader
Discrete Optimization Unit
RIKEN Center for Advanced Intelligence Project


1030-1130, 24 Jun 2019


SCT909, Cha Chi Ming Science Tower, Ho Sin Hang Campus


Many real-world problems, including machine-learning and data-mining applications, can be formulated as combinatorial optimization problems. Such a problem often contains stochastically uncertain parameters, and we are required to find a solution under the uncertainty.

Here, we consider "optimization with queries" setting. In this setting, we can conduct a query to a parameter to remove its uncertainty. If we conduct queries to all the parameters, the problem is reduced to a non-stochastic problem (omniscient problem). Thus, our goal is to find a query strategy such that after conducting the queries, we can get a solution that has comparable quality to the omniscient solution. In this talk, we show that a property related to a "local search" forms a sufficient condition to the existence of a good query strategy.

(This is a joint work with Yutaro Yamaguchi from Osaka University, Japan)


Dr. Takanori Maehara is a Unit Leader at Discrete Optimization Unit, RIKEN Center for Advanced Intelligence Project, Japan. He received his PhD from the University of Tokyo in 2012. His research interests include discrete mathematics (graph algorithms, submodularity, etc), and machine learning (learning theory and explanability of AI).