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

2015/05/22 by Coralia Cartis, Cartis, Coralia, Katya Scheinberg +1 · 12 citations
Computer Science · Mathematics · #Advanced Multi-Objective Optimization Algorithms #Advanced Optimization Algorithms Research #math.OC #msc:90C30 #msc:90C56

paper · pdf · doi:10.48550/arxiv.1505.06070

arxiv created 2017/01/05 · arxiv updated 2017/01/06

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

Citations

• A Stochastic Approximation Method
• Sample size selection in optimization methods for machine learning
• First-order methods of smooth convex optimization with inexact oracle

Cited by

• A Parameter-Free Stochastic LineseArch Method (SLAM) for Minimizing Expectation Residuals
• OFF (Proximal) Newton-type Methods with Inexact Derivatives for Unconstrained Optimization
• Stochastic Adaptive Optimization with Unreliable Inputs: A Unified Framework for High-Probability Complexity Analysis
• A Progressive Batching L-BFGS Method for Machine Learning
• On Complexity of Model-Based Derivative-Free Methods
• A line search framework with restarting for noisy optimization problems
• Sequential test sampling for stochastic derivative-free optimization
• Recursive Bound-Constrained AdaGrad with Applications to Multilevel and Domain Decomposition Minimization
• Gradient-Normalized Smoothness for Optimization with Approximate Hessians
• A variable dimension sketching strategy for nonlinear least-squares
• A Structured Tour of Optimization with Finite Differences
• Stochastic Subspace Descent Accelerated via Bi-fidelity Line Search

Related

• Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective
• ProGO: Probabilistic Global Optimizer
• Universal regularization methods - varying the power, the smoothness and the accuracy
• Convergence of trust-region methods based on probabilistic models