ORIE’s Scheinberg, colleagues win INFORMS’ Best Simulation Publication Award

ORIE Professor Katya Scheinberg and her co-authors have received the INFORMS Simulation Society’s Outstanding Publication Award for 2021.

The paper—authored by Scheinberg, Jose Blanchet (Stanford), Coralia Cartis (Oxford), and Matt Menickelly (Argonne National Laboratory)—is titled “Convergence Rate Analysis of a Stochastic Trust-Region Method via Supermartingales” and appeared in INFORMS Journal on Optimization, 1(2) (2019), 92-119.

“I am excited to have received this award,” Scheinberg said. “This paper took significant effort by an interdisciplinary team which helped us to develop results that we are proud of.  I am very grateful to my co-authors for this collaboration.”

Iterative simulation-based stochastic optimization algorithms are a very important class of tools not only in the simulation community, but in many other areas including machine learning, where they are really a central tool for learning good neural network parameters. Their convergence has been analyzed at length in certain cases, such as for the classical stochastic approximation method under certain simplifying assumptions. But the methods that currently work well in large applications such as machine learning are more complicated and the simplifying assumptions typically do not hold. Stochastic trust-region methods with adaptive step sizes, can have several variants that are hard to analyze theoretically.

This paper provides a general framework for rigorous convergence analysis of such methods in terms of the expected number of iterations required to reach a neighborhood of the optimal solution, in a very general setting that covers many algorithms, under the assumption that the gradient (or Hessian, in the second-order case) can be estimated with sufficient accuracy. The analysis uses Lyapunov functions and martingale analysis to provide bounds on the expected number of iterations. The approach can potentially apply to many other simulation-optimization algorithms. This paper has attracted a lot of interest in both the machine learning and optimization communities. It is among a set of papers by some of these authors on the convergence of these types of stochastic optimization algorithms in slightly different frameworks. These papers together constitute a very important and impactful contribution overall.

Other Articles of Interest