Sep. Oct. 2017 Nov.
01 020304050607
1516 1718192021
22 232425262728
Click Seminar

Past Seminars

DateJuly 3, 2017 (Monday)
SpeakerTasuku Soma 
ProfileThe University of Tokyo
TitleRegret Ratio Minimization in Multi-objective Submodular Function Maximization 
Submodular function maximization has numerous applications in machine learning and artificial intelligence. Many real applications require multiple submodular objective functions to be maximized, and it is not known in advance which of the objective functions is regarded to be important by a user. In such cases, it is desirable to have a small family of representative solutions that would satisfy any user’s preference. A traditional approach for solving such a problem is to enumerate the Pareto optimal solutions. However, owing to the massive number of Pareto optimal solutions (possibly exponentially many), it is difficult for a user to select a solution. In this paper, we propose practical methods with theoretical guarantees for finding a small family of representative solutions, based on the notion of regret ratio. This is joint work with Yuichi Yoshida.