Query Complexity of Derivative-Free Optimization

Abstract

This paper provides lower bounds on the convergence rate of Derivative Free Optimization (DFO) with noisy function evaluations, exposing a fundamental and unavoidable gap between the performance of algorithms with access to gradients and those with access to only function evaluations. However, there are situations in which DFO is unavoidable, and for such situations we propose a new DFO algorithm that is proved to be near optimal for the class of strongly convex objective functions. A distinctive feature of the algorithm is that it uses only Boolean-valued function comparisons, rather than function evaluations. This makes the algorithm useful in an even wider range of applications, such as optimization based on paired comparisons from human subjects, for example. We also show that regardless of whether DFO is based on noisy function evaluations or Boolean-valued function comparisons, the convergence rate is the same.

Cited by in corpus (12)

• On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization
• Simple Complexity Analysis of Simplified Direct Search
• Unimodal Bandits without Smoothness
• A One-bit, Comparison-Based Gradient Estimator
• Zeroth-order Asynchronous Doubly Stochastic Algorithm with Variance Reduction
• Stochastic Zeroth Order Gradient and Hessian Estimators: Variance Reduction and Refined Bias Bounds
• Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods
• Best Arm Identification with Safety Constraints
• Learning from Noisy Similar and Dissimilar Data
• Parallel Distributed Block Coordinate Descent Methods based on Pairwise Comparison Oracle
• Optimal Stochastic Nonconvex Optimization with Bandit Feedback
• Lower Bounds on the Complexity of Solving Two Classes of Non-cooperative Games