Source-linked AI summary
Query Complexity of Derivative-Free Optimization
Kevin G. Jamieson, Robert D. Nowak, Benjamin Recht
TL;DR
Noisy derivative-free optimization has an unavoidable convergence gap relative to gradient-based methods, motivating lower bounds for both noisy evaluations and Boolean comparisons. The paper then gives a comparison-only algorithm for strongly convex objectives whose rate is optimal in T and near-optimal in dimension, while identifying assumptions and dimension dependence that remain unresolved.
Problem
The paper asks how fast derivative-free optimization can converge when only noisy function evaluations or probably correct Boolean comparisons are available, rather than gradients.
Method
The paper proves lower bounds for both oracle models and constructs a derivative-free coordinate-descent algorithm using Boolean function comparisons.
Results
The expected error decays at the lower-bound rate under both oracle models, while the proposed algorithm is tight in T and within a factor of n in dimension.
Takeaways & Limitations
Boolean comparisons can support derivative-free optimization at the same convergence-rate dependence on T as noisy evaluations, with near-optimal dimension dependence.
Takeaways & Limitations
The dimension gap remains unresolved, and the algorithm’s analysis relies on strong convexity with Lipschitz gradients and currently assumes unconstrained optimization.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper shows that noisy function evaluations fundamentally limit derivative-free optimization: strongly convex problems incur an Ω(1/T) error lower bound, unlike the stronger rates available to noisy gradient methods. It also introduces a comparison-based algorithm that attains this T-rate near-optimally in dimension.
- Noisy function evaluations make the optimization error of every DFO method at least Ω(1/T), even for strongly convex functions.This rules out matching noisy gradient methods through finite differencing.
- Noisy gradient methods achieve Θ(1/T) error scaling for strongly convex functions, whereas noisy DFO cannot achieve their rates through finite differencing.
- A new derivative-free algorithm uses only Boolean comparisons of function values rather than numerical evaluations.This supports applications where an oracle can only decide which configuration is better.
- The comparison-based algorithm achieves the lower-bound convergence rate with near-optimal dependence on the ambient dimension.The result is relevant to paired-comparison settings such as human-subject feedback.
2 Problem formulation and background
The paper formulates DFO as minimizing an unknown strongly convex, smooth function through either noisy evaluations or noisy pairwise comparisons. Comparison reliability may depend on the objective-value gap, and the framework connects these oracles to practical human and algorithmic feedback settings.
- The objective belongs to the class of strongly convex functions with Lipschitz gradients on a convex domain and is not explicitly known.The optimization procedure can access it only through oracle queries.
- A function-evaluation oracle returns a noisy observation with zero mean and variance σ^2.
- A function-comparison oracle returns a binary random variable indicating which of two queried points is better, with reliability governed by κ, µ, and δ0.For κ > 1, reliability decreases as the objective-value difference shrinks.
- When κ = 1, comparisons are correct with probability greater than 1/2 independently of the queried points; for κ > 1, correctness depends on their function-value difference.
- With Gaussian additive evaluation noise, comparing noisy evaluations yields a comparison oracle with κ = 2.This connects numerical evaluation noise to the paper’s pairwise-comparison model.
- Pairwise comparisons are motivated by derivative-free procedures and applications involving human feedback, such as tuning prescription lenses, hearing aids, or web-search algorithms.
- The paper positions its stochastic DFO analysis against established noiseless DFO and stochastic-gradient results, identifying stochastic DFO lower bounds as a knowledge gap.
3 Main results
The main results establish lower bounds for both comparison and evaluation oracles and provide a coordinate-descent algorithm for comparison feedback. The upper bound matches the iteration and noise dependence but retains worse dimension dependence, while broader function classes remain open.
- Lower bounds: The comparison-oracle lower bound applies to estimators using at most T queries, uniformly over the strongly convex function class and admissible comparison oracles.The constants are independent of T and n.
- Upper bounds: A coordinate-descent algorithm adaptive to unknown κ provides an upper bound for unconstrained optimization using T function-comparison queries.
- Upper bounds: The comparison-based upper bound has only poly-logarithmic dependence on T, n, and 1/δ in its constants.
- Evaluation oracle: The function-evaluation lower bound applies to all estimators using T noisy evaluations over the same strongly convex function class.Its constant is independent of T and n.
- Evaluation oracle: For typical evaluation oracles such as additive Gaussian noise, the comparison-based algorithm matches the convergence rate in T and σ^2 but has worse dependence on dimension n.
- Open scope: For less restrictive convex-Lipschitz classes, prior stochastic DFO rates are weaker or dimension-polynomial, and whether the stronger rates extend remains open.
4 Lower Bounds
The lower-bound analysis uses minimax constructions over separated strongly convex functions and bounds the information available through noisy comparisons or evaluations. These constructions establish limits on identifying the minimizer under the respective oracle models.
- Minimax construction: The proofs reduce optimization to selecting among functions whose minimizers are separated in a semi-distance.The semi-distance is the Euclidean distance between function minimizers.
- Minimax construction: The hard-function family is built from well-separated vertices of a high-dimensional hypercube.A Varshamov-Gilbert construction supplies exponentially many candidate functions with separated minimizers.
- Comparison oracle: For noisy comparisons, the proofs bound distinguishability using KL divergence under a Markovian query process.The query sequence may be generated adaptively, while each oracle response is conditionally independent of earlier queries given the current pair.
- Evaluation oracle: The evaluation-oracle lower bound uses the same hard functions with additive independent noise and bounds the resulting observation distributions.The proof specializes the noise calculation to Gaussian evaluations before applying the minimax argument.
5 Upper bounds
The proposed upper-bound algorithm performs randomized coordinate descent with approximate pairwise-comparison line searches. Strong convexity and Lipschitz gradients yield expected decrease, while repeated comparisons make the search robust to oracle errors.
- Coordinate descent: The algorithm randomly selects a coordinate and performs an approximate line search along that direction.The analyzed direction is a uniformly random coordinate, although the text notes that random unit-sphere directions admit the same result.
- Coordinate descent: Strong convexity with Lipschitz gradients guarantees sufficient expected objective decrease from the approximate line search.The convergence argument combines the directional update with bounds from Lipschitz gradients and strong convexity.
- Convergence guarantee: Theorem 5 bounds the expected optimization error after K pairwise comparisons when each line search is within η of its optimum.The expectation is over the random search directions.
- Robust line search: The line search uses a binary-search-like procedure in the noiseless case and repeatedly queries comparisons when responses may be incorrect.The robust procedure uses repeated queries to infer the uncorrupted comparison direction with high confidence.
- Robust line search: Sampling multiple locations handles cases where comparison reliability depends on the magnitude of function-value differences.The procedure is designed to maintain a lower bound on comparison reliability when κ > 1.
6 Conclusion
The paper establishes lower bounds for derivative-free optimization with noisy evaluations and noisy comparisons, then gives an upper bound that is tight in iteration dependence but not fully in dimension. Several extensions remain open.
- Main conclusions: The lower bounds apply to both noisy function evaluations and probably correct Boolean comparisons.They are proved for strongly convex functions and therefore also apply to broader function classes containing them.
- Main conclusions: The proposed algorithm achieves a near-matching rate for strongly convex functions with Lipschitz gradients under both oracle models.The upper bound is within no more than a factor of n in dimension while matching the dependence on iterations T.
- Open questions: The remaining gap concerns the dependence on dimension between the lower and upper bounds.The conclusion identifies resolving this gap as an open question.
- Open questions: Further open problems include constrained domains and removing or weakening the strong-convexity and Lipschitz-gradient assumptions.The paper also calls for a practical algorithm that achieves the lower bounds without these limiting assumptions.
A Bounds on (κ, µ, δ0) for some distributions
The paper relates noisy function evaluations to comparison reliability for Gaussian and two-sided gamma noise models. These examples show that the comparison-noise parameter can span the stated range, although the supplied bound may be loose.
- Gaussian noise: For Gaussian additive noise, the comparison oracle’s correctness probability can be lower bounded from the noise variance.The derivation standardizes the Gaussian noise and integrates a lower bound on the standard-normal density.
- Two-sided gamma noise: A two-sided gamma distribution includes the Laplace distribution as the α = 1 case and has variance σ2 = α/β2.The distribution is unimodal only for α ∈ (0, 1].
- Implication: The corresponding comparison-probability bound is sufficient to realize the full range κ ∈ (1, 2].The paper notes that the bound immediately preceding this conclusion can be loose.
B Upper Bounds - Extended
The proposed derivative-free upper-bound algorithm selects a coordinate uniformly at random and performs an approximate line search at each iteration, leveraging strong convexity and Lipschitz gradients.
- Each iteration selects one of the n coordinates uniformly at random before performing an approximate line search.
B.1 Coordinate descent algorithm
The coordinate-descent analysis bounds expected suboptimality for strongly convex objectives by combining random coordinate selection, smoothness, and line-search progress.
- Theorem 7 analyzes an estimate xK of the unique minimizer x∗ after at most K pairwise comparisons.
- The expectation in the guarantee is taken over the random choice of the search direction at each iteration.
- Lipschitz gradients yield a quadratic upper bound along each randomly selected direction.
- Strong convexity makes x∗ unique and supports the expected-progress argument for the coordinate updates.
- The resulting bound specifies how many pairwise comparisons suffice to achieve expected error at most ǫ.
B.2 Line search
The line-search procedure minimizes the objective along a one-dimensional search direction using pairwise comparisons, with separate handling for large and small minimizer locations.
- The line search produces a sequence of scalar iterates while distinguishing its indexing from the outer optimization iterates.
- The one-dimensional algorithm expands and contracts an interval using pairwise comparisons to locate an approximate minimizer.
- Theorem 8 guarantees an η-accurate estimate of the line minimizer after a bounded number of comparisons in the noiseless case.
- When |α∗| is at least one, strong convexity controls the search after the initial expansion loops.
- The case |α∗| at most one is handled separately, and the two comparison bounds are combined for sufficiently small η.
- The line-search comparison complexity is summarized by logarithmic bounds in the target accuracy and search parameters.
B.3 Proof of Theorem 2
The robust line search replaces noiseless comparisons with repeated sampling, preserving the convergence rate up to constants and logarithmic factors while accounting for comparison uncertainty.
- Figure 3 estimates the mean comparison outcome by repeatedly querying the comparison random variable.
- Because noisy function differences may be arbitrarily small, the robust procedure samples four points per iteration to maintain a usable comparison margin.
- Parallel repeated-sampling procedures compare neighboring search locations and continue with the location whose procedure terminates first.
- The robust line search removes at least one-third of the search space per iteration, versus one-half in the noiseless case, so its iteration count differs only by a constant factor.
- The worst sampling cost occurs when compared function values are closest, requiring bounds based on strong convexity and the line-search accuracy.
- A union bound over repeated subroutine calls controls the total comparison budget with probability at least 1−δ.
- Choosing the accuracy parameter to ensure expected optimization error at most ǫ yields the stated convergence rate as a function of T and σ2.