Jose Blanchet, Coralia Cartis, Matt Menickelly, Katya Scheinberg (2019) Convergence Rate Analysis of a Stochastic Trust-Region Method via Supermartingales. INFORMS Journal on Optimization 1(2):92-119. https://doi.org/10.1287/ijoo.2019.0016

View Publication

Abstract

We propose a novel framework for analyzing convergence rates of stochastic optimization algorithms with adaptive step sizes. This framework is based on analyzing properties of an underlying generic stochastic process; in particular, we derive a bound on the expected stopping time of this process. We utilize this framework to analyze the expected global convergence rates of a stochastic variant of a traditional trust-region method. Although traditional trust-region methods rely on exact computations of the gradient, Hessian, and values of the objective function, this method assumes that these values are available only up to some dynamically adjusted accuracy. Moreover, this accuracy is assumed to hold only with some sufficiently large—but fixed—probability without any additional restrictions on the variance of the errors. This setting applies, for example, to standard stochastic optimization and machine learning …

Authors: Jose Blanchet, Coralia Cartis, Matt Menickelly, Katya Scheinberg
Publication date: 2019/4
Journal: INFORMS journal on optimization
Volume: 1
Issue: 2
Pages: 92-119
Publisher: INFORMS