SeqALO

The goal of this project is to develop a new complexity theory for sequential and active optimization, to implement it in industrial projects, and to teach the students of Ecole Normale Supérieure de Lyon the theory and practice of sequential decision making in particular and machine learning in general. An agent is given a stochastic numeric code f:X*E?R where X is a set of controllable variables and E a probability space representing the uncontrollable variables. At time t, she chooses a control x_t according to all past observations, and observes f(x_t,w) for some random w of E. What is the best possible strategy so as to optimize x->F[f(x, .)], where F is some utility function (eg. expectation)? We consider the PAC setting, with a given risk d and a tolerance parameter e. In the simplistic case where X is a finite set, f can be any function and F is the mean, I have shown with my co-author and former student Emilie Kaufmann that identifying e-optimal x with probability at least 1-d requires at least T(f)*log(1/d) observation points, where T(f) is the information-theoretic optimization complexity of the function. Besides, we have proposed an algorithm (called Track-and-Stop) achieving this rate (with multiplicative constant 1) when d is small. The goal of this project is to develop this theory so as to face more realistic problems. First, risk-sensitive applications such as agronomy require to consider other utility functions. Second, many cases like clinical trial naturally encompass some structure on the set X, and restrictions on the set of possible functions f. For example, F[f(x, .)] can be known in advance to be monotonous, unimodal, or slowly varying (two consecutive point means cannot differ by more than a prescribed quantity). Third, in cases like recommender systems, the set X can be huge but its graph structure can be used to accelerate a lot optimization. Fourth, the space X can be continuous (as for example certain parameters in autoML); we will address this case by combining our analysis of the second and of the third cases with classical non-parametric ideas. This chair also aims at developing the teaching of artificial intelligence at Ecole Normale Supérieure de Lyon, a very selective institution with a limited number of extremely motivated students willing to train for research. This is an important aspect of my mission since I was recruited, last year, at the intersection of the mathematics and computer science departments. Rely on existing very good programs in theoretical computer science and in general mathematics, I want to grow a group of statistical learning specialists every year, with a strong background in mathematical statistics and learning theory in general, and a specialization in noisy optimization and computer experiments in particular. This project develops a field of expertise of the French research. This approach of optimization has shown very successful over the past ten years, and is one of the building blocks of significant recent successes of AI: personalized search engines, recommender and ads systems, reinforcement learning and MCTS, online auction systems, autoML, etc. The present project is relevant to all those fields and will have a great impact by both providing a general theoretical notion of complexity of noisy optimization, and a new algorithms or meta-algorithms for solving practical tasks. This project is part of the academic program in Machine Learning of the University of Lyon and Saint-Etienne, now united in the research federation SciDoLySE. This federation encourages joint work among all its participants: in addition to UMPA and LIP, I can rely on and propose collaboration with my colleagues from Institut Camille Jordan, Dante INRIA team and Laboratoire Hubert Curien (to name just a few), and to disseminate the research and training fruits of my project to the entire site.