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

2015/05/22 by Coralia Cartis, Cartis, Coralia, Katya Scheinberg +1 · 7 citations
Mathematics · Computer Science · #Advanced Optimization Algorithms Research #Advanced Multi-Objective Optimization Algorithms

paper · pdf · doi:10.48550/arxiv.1505.06070

Abstract

We present global convergence rates for a line-search method which is based\non random first-order models and directions whose quality is ensured only with\ncertain probability. We show that in terms of the order of the accuracy, the\nevaluation complexity of such a method is the same as its counterparts that use\ndeterministic accurate models; the use of probabilistic models only increases\nthe complexity by a constant, which depends on the probability of the models\nbeing good. We particularize and improve these results in the convex and\nstrongly convex case.\n We also analyze a probabilistic cubic regularization variant that allows\napproximate probabilistic second-order models and show improved complexity\nbounds compared to probabilistic first-order methods; again, as a function of\nthe accuracy, the probabilistic cubic regularization bounds are of the same\n(optimal) order as for the deterministic case.\n

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

Related

• Global Convergence Rate Analysis of a Generic Line Search Algorithm with\n 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\n the accuracy
• Convergence of trust-region methods based on probabilistic models