INRIA

Machine learning has grown significantly in the last two decades and have had impact in diverse areas such as computer vision, natural language processing, computational biology and social sciences. These new applications have made apparent though that real world data have a richer structure than have been modeled by some of the classical paradigms of machine learning such as binary classification and regression. In machine translation for example, the algorithm needs to choose amongst an exponential number of possible sequences of words as translations, and not just a few options as in handwritten digits recognition. A key challenge in modern machine learning is to find ways to model this complex structure in a scalable manner which is still robust to model misspecification. In this talk, I will present such a method that can exploit the combinatorial structure in data represented by graphs, with various applications such as the task of word alignment in natural language processing, the alignment of large knowledge bases for the Semantic Web or the tracking of multiple objects in video. I will also present how these problems have motivated progress on novel optimization techniques including improvements on the venerable Frank-Wolfe optimization algorithm (1956) or Robbins-Monroe stochastic gradient method (1951). These examples will highlight how the rich two-way street between optimization and machine learning enables us to exploit more effectively the structure of complex data.