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

Journal article

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 analyze 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.

Authors: Cartis, C; Scheinberg, K

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer Berlin Heidelberg
• Journal: Mathematical Programming
• Volume: 169
• Issue: 2
• Pages: 337–375
• Publication date: 2017-04-01
• Acceptance date: 2017-03-22
• DOI: 10.1007/s10107-017-1137-4
• EISSN: 1436-4646
• ISSN: 0025-5610
• Keywords: line-search methods; global convergence analysis; cubic regularization methods; random models