Winner
Haihao (Sean) Lu (Booth School of Business, University of Chicago) for the paper titled “An O(s^r)-Resolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems”.
Citation
There has been renewed interest in using ordinary differential equations (ODEs) to understand the dynamics of a discrete-time optimization algorithm (DTA), due to the ease of analysis of ODEs compared to that of a DTA. However, two fundamental open questions have limited the applications of the ODE approach in optimization algorithm analysis: 1) how to obtain a suitable ODE from an optimization method? 2) what is the connection between the convergence of the ODE and the convergence of the optimization method? Haihao Lu’s paper constructively answers the first question by proposing a hierarchy of O(s^r)-resolution ODEs, parameterized by the order r, that converges to the discrete-time optimization method as r goes to infinity, where s is the step-size of the algorithm. Furthermore, the paper addresses the second question by showing that with a properly chosen energy function in the analysis, the linear convergence of the ODE automatically guarantees the linear convergence of the corresponding optimization method. Finally, the paper answers fundamental questions about three central algorithms for minimax problems and their convergent/divergent behavior. In summary, the novel and unified framework developed in this paper for analyzing a broad class of optimization algorithms makes it highly deserving of the INFORMS Optimization Society Young Researcher Prize.
Prize committee
Simge Küçükyavuz (chair), Illya V. Hicks, Guanghui (George) Lan, Alberto Del Pia