(Maths-IA) Geometrical and computational complexity of bilevel optimization

Bilevel optimization is useful in machine learning to tackle problems such as hyperparameter tuning, metalearning or even optimal transport problems. However it presents theoretical and computational challenges, particularly in the nonconvex setting. This talk presents recent advances that may improve our understanding of the complexity, algorithmic strategies, and statistical properties of bilevel problems. We establish the hardness of smooth bilevel programs by showing their equivalence to general lower semicontinuous minimization and proving that polynomial bilevel problems are Σ_p^2-hard (harder than NP-hard). This a joint work with J. Bolte, Q. T. Le & E. Pauwels.