Sponsored by the INFORMS Simulation Society, the award recognizes exceptional contributions to the simulation literature in the form of articles, books, book chapters and monographs, copyrighted between 2017 and 2019.
In their award-winning paper “Convergence Rate Analysis of a Stochastic Trust-Region Method via Supermartingales,” published in the INFORMS Journal of Optimization in 2019, the researchers propose a framework for analyzing convergence rates of stochastic optimization methods by viewing the iterative optimization method as a stochastic process. They apply this framework to a stochastic trust-region optimization with random models (STORM) technique. Specifically, they use their new framework to derive a bound on the convergence rate of STORM, initially to first-order and then extended to second-order critical points.
Why stochastic optimization?
Stochastic optimization methods have received increasing attention by the optimization community, especially in applications involving machine learning. Recent successes in such applications have led to increased interest in nonconvex optimization – and with it a growing interest in trust-region methods for training nonconvex models. Although several methods have been proposed, these typically rely on a finite dataset fixed before optimization.
“In contrast, our approach uses trust-region methods with adaptive sampling in a fully stochastic setting,” said Matt Menickelly, an assistant computational mathematician in Argonne’s Mathematics and Computer Science division and one of the authors of the paper. “To the best of our knowledge, this is the first analysis of trust-region methods in such a setting.”
Benefits
The main contribution of the paper is to provide a rigorous theoretical framework for bounding the expected complexity of a stochastic optimization method. The convergence rate of a variety of algorithms can potentially be analyzed by using the new general framework. Menickelly is currently developing variational hybrid quantum-classical algorithms similar to STORM, using the theory in this paper to ensure simultaneous measurement frugality and accuracy on noisy intermediate-scale quantum devices.
For the full paper, see Jose Blanchet, Coralia Cartis, Matt Menickelly, and Katya Scheinberg, “Convergence Rate Analysis of a Stochastic Trust-Region Method via Supermartingales,” INFORMS Journal on Optimization 1(2) Spring 2019, pp. 92—118≈ https://pubsonline.informs.org/doi/pdf/10.1287/ijoo.2019.0016