Variable metric random pursuit

We consider unconstrained randomized optimization of smooth convex objective functions in the gradient-free setting. We analyze Random Pursuit (RP) algorithms with fixed (F-RP) and variable metric (V-RP). The algorithms only use zeroth-order information about the objective function and compute an ap...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2016-03, Vol.156 (1-2), p.549-579
Main Authors: Stich, S. U., Müller, C. L., Gärtner, B.
Format: Article
Language:English
Subjects:
Adaptation
Algorithms
Approximation
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Computer engineering
Computer programming
Computer science
Convergence
Convex analysis
Filtering
Filtration
Full Length Paper
Mathematical analysis
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematical models
Mathematical programming
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Optimization
Studies
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider unconstrained randomized optimization of smooth convex objective functions in the gradient-free setting. We analyze Random Pursuit (RP) algorithms with fixed (F-RP) and variable metric (V-RP). The algorithms only use zeroth-order information about the objective function and compute an approximate solution by repeated optimization over randomly chosen one-dimensional subspaces. The distribution of search directions is dictated by the chosen metric. Variable Metric RP uses novel variants of a randomized zeroth-order Hessian approximation scheme recently introduced by Leventhal and Lewis (Optimization 60(3):329–345, 2011 . doi: 10.1080/02331930903100141 ). We here present (1) a refined analysis of the expected single step progress of RP algorithms and their global convergence on (strictly) convex functions and (2) novel convergence bounds for V-RP on strongly convex functions. We also quantify how well the employed metric needs to match the local geometry of the function in order for the RP algorithms to converge with the best possible rate. Our theoretical results are accompanied by numerical experiments, comparing V-RP with the derivative-free schemes CMA-ES, Implicit Filtering, Nelder–Mead, NEWUOA, Pattern-Search and Nesterov’s gradient-free algorithms.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-015-0908-z