Variable metric random pursuit

Sebastian U. Stich, Christian L. Müller, Bernd GärtnerMath. Program 2016 · OpenReview

TL;DR

This paper introduces "Variable Metric Random Pursuit" (V-RP), a novel gradient-free optimization algorithm that adaptively learns the local geometry of a function to improve search direction. V-RP achieves near-optimal convergence rates on strongly convex functions, outperforming many existing derivative-free methods, especially in challenging, ill-conditioned scenarios.

What Problem Does This Paper Address?

Optimizing complex functions without access to their gradients (gradient-free optimization) is crucial in many real-world applications where derivatives are unavailable or computationally expensive. While randomized search methods like Random Pursuit (RP) are promising, their efficiency often suffers when the function's "shape" (its curvature) varies significantly across different directions. Standard RP uses a fixed, isotropic search distribution, which can be slow if the function is highly elongated in certain directions. This paper addresses the challenge of making gradient-free optimization more efficient by allowing the search strategy to adapt to the function's local geometry, aiming for faster convergence, especially for strongly convex functions.

Methods

The core contribution is the development of Variable Metric Random Pursuit (V-RP). This algorithm builds upon the Random Pursuit (RP) framework, which iteratively optimizes along randomly chosen one-dimensional subspaces. The key innovation in V-RP is the introduction of a variable metric that guides the sampling of these search directions. This metric is an approximation of the inverse Hessian of the objective function.

V-RP employs a Randomized Hessian Estimation (RHE) scheme, drawing from recent work by Leventhal and Lewis. This RHE scheme iteratively updates an approximation of the Hessian. The V-RP algorithm then uses this learned metric (specifically, its inverse as a covariance matrix) to sample search directions that are more aligned with the function's local curvature. The paper provides both theoretical analysis of V-RP's convergence rates and novel implementations of the RHE scheme.

The paper also analyzes Fixed Metric Random Pursuit (F-RP), a baseline where the metric is constant, to establish theoretical foundations. For V-RP, the authors present theoretical convergence bounds for strongly convex functions and quantify the required accuracy of the metric approximation for optimal convergence.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical experiments on synthetic benchmark functions.

Key Insights and Ideas

  • Adaptive Search is Key: The most significant insight is that adapting the search direction distribution to the function's local geometry (its "metric") dramatically improves convergence speed in gradient-free optimization, especially for ill-conditioned problems.
  • RHE as a Building Block: The paper demonstrates that Randomized Hessian Estimation (RHE) can be effectively integrated into Random Pursuit to create a powerful Variable Metric Random Pursuit (V-RP) algorithm.
  • Near-Optimal Convergence: V-RP can achieve convergence rates that are theoretically near-optimal for strongly convex functions, approaching the performance of methods that use gradient information.
  • Metric Accuracy Matters: The paper quantifies how well the learned metric needs to approximate the true Hessian to achieve these optimal rates, providing a theoretical basis for understanding the algorithm's behavior.
  • Practical Implications: The numerical experiments show V-RP outperforming many established derivative-free methods, particularly in scenarios with high curvature or ill-conditioning.

Key Results

  • Theoretical Convergence Bounds: The paper provides refined analysis of expected single-step progress and global convergence for F-RP on convex functions. Crucially, it establishes novel convergence bounds for V-RP on strongly convex functions, showing it can achieve rates close to optimal.
  • Empirical Performance: Numerical experiments comparing V-RP with algorithms like CMA-ES, Implicit Filtering, Nelder-Mead, NEWUOA, Pattern-Search, and Nesterov's gradient-free algorithms demonstrate V-RP's superiority, especially on ill-conditioned quadratic functions. For instance, on challenging quadratic functions (f3 with high curvature), V-RP achieved significantly better accuracy with fewer function evaluations compared to many other methods.
  • Adaptive Schemes Excel: The results consistently show that adaptive schemes (V-RP, CMA-ES, NEWUOA) are generally superior to non-adaptive ones, particularly when dealing with ill-conditioning.

Limitations and Future Work

  • Constrained Optimization: The authors acknowledge that extending Random Pursuit schemes to constrained optimization problems (min f(x) subject to x ∈ C) remains an open question.
  • Non-Convex Functions: Analyzing Random Pursuit for general non-convex functions, including globally convex or d-convex functions, or noisy functions with bounded variance, is another area for future research.
  • Non-Smooth Functions: Developing gradient-free optimization methods for non-smooth convex functions is identified as a fundamental challenge requiring novel tools.
  • RHE Implementations: While the paper presents three novel RHE implementations, further practical exploration and theoretical analysis of their performance and robustness could be beneficial.
  • Average Case Analysis: The paper hints at the possibility of analyzing average-case scenarios to potentially derive tighter convergence bounds, but notes this would require more detailed trajectory analysis.

Summary updated

Abstract

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.
BibTeX
@inproceedings{stich2016variable,
  author = {Sebastian U. Stich and Christian L. Müller and Bernd Gärtner},
  title = {{Variable metric random pursuit}},
  booktitle = {Math. Program},
  year = {2016},
  url = {https://openreview.net/forum?id=RtcaONFTvmO},
}
Figure