Two of the most important ingredients behind the modern techniques and tools in data science are sampling and optimization algorithms. Even more, their applicability spans the whole spectrum of computer science and engineering. The need is for algorithms amenable to efficient implementations that scale to thousands of dimensions and also have theoretical guarantees both of their running time and the quality of the output. For this we need to exploit the geometry and the structure of the input and to employ novel algorithmic techniques.
We are looking for an excellent PhD candidate to work on the intersection of optimization, high-dimensional geometry, and computational statistics. The goal is to introduce and analyze efficient randomized algorithms for the fundamental problems of high-dimensional sampling, integration and convex optimization (especially semi-definite). A focus will be given on geometric primitives and algebraic operations. We will combine tools from numerical mathematics, like algorithms for ordinary and stochastic differential equations and condition number analysis with tools from convex geometry and sampling techniques, to introduce new perspectives to classical problems.
The foundation will be the development of the basic algebraic and geometric operations for computations with convex bodies, with a primary focus on polytopes, the feasible regions of linear programs, and spectrahedra, the feasible regions of semidefinite programs. With this we will employ a rich class of geometric random walks, that in turn we use to build efficient methods for sampling points from convex bodies, under various probability distributions. These operations are the backbone of integration and optimization algorithms and fundamental for algorithmic inference.
We will study in detail the bit complexity of the primitive geometric and algebraic operations as well as the (mixing time of the) various random walks and the error bound analysis and propagation. The detailed study of these operations will allow us to introduce algorithms for optimization with precise Boolean complexity bounds and without hidden constants in the exponents.
An important direction will be the efficient implementation and the practical evaluation, through extensive experiments, of the new algorithms. The main language will be C++ but other high level languages and environments could be used (e.g. R, Python, Matlab) both for experimentation with state-of-the art software and for building high-level tools and interfaces. The software development will be based on, but not limited to, the current software tools developed in the GeomScale project.
Bibliography
The successful candidate will be a member of the OURAGAN team which is a joint team between Inria Paris and IMJ-PRG Sorbonne Université, Paris, France. We are located in the center of Paris.
The successful candidate will work with Elias Tsigaridas and Vissarion Fisikopoulos. She/he will also collaborate with Alexandre d’Aspremont and Adrien Taylor. The position is funded by Inria Paris.
When: The desired starting date is 1st October 2021.
Who: The successful candidate should be highly motivated and creative with a strong background in applied mathematics and/or computer science. Good programming skills are also required.
Deadline: Informal inquiries are strongly encouraged and the interested candidates can contact elias.tsigaridas @ inria.fr for additional details the sooner possible.
The deadline for applications is 28 May 2021. The application should include: