Stochastic Optimization with Queries

Abstract

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)

Biography

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