Convergence Rate Analysis of a Stochastic Trust Region Method via Submartingales

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 by deriving a bound on the expected stopping time of this process. We utilize this framework to analyze the bounds on expected global convergence rates of a stochastic variant of a traditional trust region method, introduced in \cite{ChenMenickellyScheinberg2014}. While 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 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 the analysis in \cite{ChenMenickellyScheinberg2014}, we show that the stochastic process defined by the algorithm satisfies the assumptions of our proposed general framework, with the stopping time defined as reaching accuracy $\Vert \nabla f(x)\Vert \le \epsilon$. The resulting bound for this stopping time is $O({\epsilon }^{-2})$, under the assumption of sufficiently accurate stochastic gradient, and is the first global complexity bound for a stochastic trust-region method. Finally, we apply the same framework to derive second order complexity bound under some additional assumptions.

arXiv comment22 pages. arXiv admin note: text overlap with arXiv:1504.04231

References in corpus (5)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Variance Reduction for Nonconvex Optimization
• Variance Reduction for Faster Non-Convex Optimization
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Convergence of trust-region methods based on probabilistic models

Cited by in corpus (10)

• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• A Stochastic Line Search Method with Convergence Rate Analysis
• Inexact Non-Convex Newton-Type Methods
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Black-Box Optimization in Machine Learning with Trust Region Based Derivative Free Algorithm
• Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization
• Learning an Astronomical Catalog of the Visible Universe through Scalable Bayesian Inference
• Stochastic Trust Region Methods with Trust Region Radius Depending on Probabilistic Models
• A note on solving nonlinear optimization problems in variable precision
• Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity