ERI: Systematic Design of Iterative Black-Box Optimization Algorithms

A vast array of problems in science and engineering center on making the best decision given the available information. From finance and marketing to transportation and healthcare, today’s data-driven society is increasingly reliant on machines that use algorithms to make decisions based on data. Traditionally, the computational resources required by an algorithm were studied on a case-by-case basis. Recent work, however, has led to a systematic methodology for algorithm analysis. In contrast, the design of algorithms is far from systematic and often involves extensive numerical computations to tune hyperparameters or insight of experts guided by computer-assisted analysis. Building on these recent advances in algorithm analysis, this project aims to develop a principled approach to algorithm design. The developed tools and insights will enable specialized and efficient algorithms to be deployed across a variety of data-driven applications. This is particularly important in large-scale, safety-critical, and embedded systems that necessitate efficient use of computational resources. Iterative algorithms can be viewed as dynamical systems, and as such are amenable to study using tools from control theory. Both the optimization and control communities have their own approaches and tools regarding algorithm analysis. The performance estimation approach in optimization, for instance, uses function interpolation to find the worst-case problem instance, while integral quadratic constraints in control represent use of an “energy” function to bound the worst-case performance over all iterations of the algorithm. By leveraging tools from both optimization and control (including interpolation, Lyapunov stability, and robust control synthesis), this project seeks to systematically design efficient algorithms based on the structure of available information and to automate the developed tools using efficient and modular software that will be made available through public dissemination. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.