Finding Global Minima via Kernel Approximations

ABSTRACT: We consider the global minimization of smooth functions based solely on function evaluations. Algorithms that achieve the optimal number of function evaluations for a given precision level typically rely on explicitly constructing an approximation of the function which is then minimized with algorithms that have exponential running-time complexity. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum. This is done by using infinite sums of square smooth functions and has strong links with polynomial sum-of-squares hierarchies. Leveraging recent representation properties of reproducing kernel Hilbert spaces, the infinite-dimensional optimization problem can be solved by subsampling in time polynomial in the number of function evaluations, and with theoretical guarantees on the obtained minimum. (Joint work with Alessandro Rudi and Ulysse Marteau-Ferey).

BIO: Francis Bach is a researcher at INRIA, leading the machine learning team, which is part of the Computer Science Department at the École normale supérieure, since 2011. He graduated from École Polytechnique in 1997 and completed his Ph.D. in Computer Science at U.C. Berkeley in 2005, working with Professor Michael Jordan. He spent two years in the Mathematical Morphology group at École des Mines de Paris; then, he was part of the computer vision project team at INRIA/École normale supérieure from 2007 to 2010. Francis Bach is primarily interested in machine learning, and especially in sparse methods, kernel-based learning, large-scale optimization, computer vision and signal processing. He obtained a Starting Grant in 2009 and a Consolidator Grant from the European Research Council in 2016; and he received the INRIA young researcher prize in 2012 and the ICML test-of-time award in 2014 and 2019, as well as the Lagrange prize in continuous optimization in 2018 and the Jean-Jacques Moreau prize in 2019. He was elected to the French Academy of Sciences in 2020. In 2015, he was program co-chair of the International Conference in Machine Learning (ICML), and general chair in 2018; he is now co-editor-in-chief of the Journal of Machine Learning Research.

Join Zoom Meeting https://umich.zoom.us/j/92211136360

Meeting ID: 922 1113 6360

Passcode: XXXXXX (Will be sent via e-mail to attendees)

Zoom Passcode information is also available upon request to Katherine Godwin ([email protected]).