Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
type: Item
instance of: scholarly article
title: Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
zbMATH Open document ID: 1407.90307
published in: Mathematical Programming. Series A. Series B
publication date: 2018-06-25T00:00:00Z
full work available at URL: https://arxiv.org/abs/1505.06070
review text: This paper studies a class of methods which have the best properties of deterministic algorithms and additionally relax the assumption that the derivative/model error is bounded in deterministic manner. In particular, the authors analyze global convergence rates for a line search method based on random models, for the cases of general nonconvex, convex and strongly convex functions. It is shown that in terms of the order of the accuracy, the evaluation complexity of such a method is the same as its counterparts that use deterministic accurate models; the use of probabilistic models only increases the complexity by a constant, which depends on the probability of the models being good. A second-order method is studied, too -- an adaptive probabilistic cubic regularization method. It is shown that this method has improved complexity bounds compared to probabilistic first-order methods and that these bounds are of the same optimal order as for the deterministic case.
Mathematics Subject Classification ID: 90C30
Mathematics Subject Classification ID: 90C56
Mathematics Subject Classification ID: 49M37
zbMATH DE Number: 6894013
zbMATH Keywords: line search methods
zbMATH Keywords: cubic regularization methods
zbMATH Keywords: random models
zbMATH Keywords: global convergence analysis
author: Coralia Cartis
author: Katya Scheinberg
reviewed by: Nada Djuranović-Miličić
MaRDI profile type: Publication
OpenAlex ID: W2137633966
arXiv ID: 1505.06070
cites work: Convergence of Trust-Region Methods Based on Probabilistic Models
cites work: Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
cites work: An inexact successive quadratic approximation method for L-1 regularized optimization
cites work: Sample size selection in optimization methods for machine learning
cites work: On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization
cites work: Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
cites work: Adaptive cubic regularisation methods for unconstrained optimization. II: Worst-case function- and derivative-evaluation complexity
cites work: Stochastic optimization using a trust-region method and random models
cites work: First-order methods of smooth convex optimization with inexact oracle
cites work: Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
cites work: Direct Search Based on Probabilistic Descent
cites work: Introductory lectures on convex optimization. A basic course.
cites work: Random gradient-free minimization of convex functions
cites work: Cubic regularization of Newton method and its global performance
cites work: A Stochastic Approximation Method
cites work: Q4861446
cites work: Multivariate stochastic approximation using a simultaneous perturbation gradient approximation
DOI: 10.1007/S10107-017-1137-4
Recommended article: Rates of Convergence for a Class of Global Stochastic Optimization Algorithms
Recommended article: Global convergence of a class of unconstrained optimal methods that include the conjugate descent method
Recommended article: Convergence analysis of a global optimization algorithm using stochastic differential equations
Recommended article: On the Global Convergence of Derivative-Free Methods for Unconstrained Optimization
Recommended article: Global convergence of nonmonotone descent methods for unconstrained optimization problems
Recommended article: Q5215146
Recommended article: Globally convergent algorithms for unconstrained optimization
Recommended article: Globally convergence of nonlinear conjugate gradient method for unconstrained optimization
Recommended article: Q3219705
Recommended article: Q5465352
description: scientific article