Convergence Rate Analysis of a Stochastic Trust-Region Method via Supermartingales
INFORMS Journal on Optimization · 2019-04 · 1 (2) · 92-119
DOI: 10.1287/ijoo.2019.0016 ↗Kurz gefasst
Fachartikel in der Zeitschrift INFORMS Journal on Optimization, 2019-04. Verfasst von Jose Blanchet und 3 weiteren Autor:innen. Die Arbeit wurde bisher 90-mal zitiert (Crossref) und nennt 16 Literaturangaben.
Abstract (Originalsprache)
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 formulations. Improving upon prior analysis, we show that the stochastic process defined by the trust-region method satisfies the assumptions of our proposed general framework. The stopping time in this setting is defined by an iterate satisfying a first-order accuracy condition. We demonstrate the first global complexity bound for a stochastic trust-region method under the assumption of sufficiently accurate stochastic gradients. Finally, we apply the same framework to derive second-order complexity bounds under additional assumptions.
Zitieren
APA
Blanchet, J., Cartis, C., Menickelly, M., & Scheinberg, K. (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
Vancouver
Blanchet J, Cartis C, Menickelly M, Scheinberg K. Convergence Rate Analysis of a Stochastic Trust-Region Method via Supermartingales. INFORMS Journal on Optimization. 2019;1(2):92-119. doi:10.1287/ijoo.2019.0016
BibTeX
@article{Blanchet2019,
author = {Blanchet, Jose and Cartis, Coralia and Menickelly, Matt and Scheinberg, Katya},
title = {Convergence Rate Analysis of a Stochastic Trust-Region Method via Supermartingales},
journal = {INFORMS Journal on Optimization},
year = {2019},
volume = {1},
number = {2},
pages = {92--119},
doi = {10.1287/ijoo.2019.0016}
}
EUVIMED