Optimization Online


Global convergence rate analysis of unconstrained optimization methods based on probabilistic models

Coralia Cartis(coralia.cartis***at***maths.ox.ac.uk )
Katya Scheinberg(katyascheinberg***at***gmail.com)

Abstract: We present global convergence rates for a line-search method which is based on random first-order models and directions whose quality is ensured only with certain probability. We show 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. We particularize and improve these results in the convex and strongly convex case. We also analyse a probabilistic cubic regularization variant that allows approximate probabilistic second-order models and show improved complexity bounds compared to probabilistic first-order methods; again, as a function of the accuracy, the probabilistic cubic regularization bounds are of the same (optimal) order as for the deterministic case.

Keywords: line-search methods, cubic regularization methods, random models, global convergence analysis

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Citation: Lehigh University, May 2015

Download: [PDF]

Entry Submitted: 05/22/2015
Entry Accepted: 05/22/2015
Entry Last Modified: 05/22/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society