Auditorium (Building IMAG)
8 January 2019 - 14h00
The power of graphs in speeding up online learning and decision making
by Michal Valko from SequeL, Inria Lille - Nord Europe
Abstract: I will describe adaptive solutions of using graphs for efficiently encoding, discovering, and using the (extra) information that is either explicitly or implicitly present in a given environment. This information can be, smoothness, side observations, state-spaces similarities, or a favorable reward structure which makes the learning faster or easier. I will focus exclusively on online learning and decision making to discuss the necessary tradeoffs that emerge but also when best-of-all-worlds behavior is possible. In particular, I will treat the tradeoffs of representation capacity vs. speed (computational complexity) and capacity vs. learning (statistical complexity) and discuss the optimal allocation of resources. I give specific examples of applying graphs in concrete products (patient data, face recognition, and recommender systems. Finally, I will give solutions for distributed computation with graphs and approximations needed when facing massive data. To sum up, while in the last decade we have been witnessing a huge leap in learning (with) low-level representations such as in vision, the high-level cognition remains a challenge. Graphs offer a natural representation and in this talk, I will attempt to convince you that they can be used to improve also systems working with low-level representations.