Computing the exact performance of black-box optimization methods: an automated tool to improve understanding and design better algorithms

Optimization algorithms are used everywhere in applied mathematics, where they help minimize consumption or cost, or maximize impact or profit, in a large variety of applications across the sciences, engineering, industry and business; they also lie at the core of most machine learning techniques. Algorithms that perform the best in practice are frequently those for which we possess a good theoretical understanding. In particular, one usually seeks to analyze the worst-case behavior of a given algorithm on a typical class of input problems which, once identified and formally proved, provides strong guarantees on its performance (such as accuracy after a certain number of iterations). Designing mathematical convergence proofs is a highly non trivial process that requires creativity, and often only identifies non tight bounds. However, a completely different approach as recently introduced where the problem of identifying worst-case was itself posed as an optimization problem, which can be effectively computed for a large class of optimization algorithms and input problems (including first-order methods applied to convex problems). Analyzing these algorithms in such situations can be therefore be completely automated, leading to effortless proofs and useful insight on the worst-case functions. This project will investigate three complementary directions in this new field of performance estimation: (1) first, one will investigate larger classes of input problems, abandoning the convexity requirement (2) second, the framework will be generalized to allow other types of algorithms beyond deterministic first-order methods, (3) third, this approach will be leveraged to design novel methods that achieve the best possible performance.