Source-linked AI summary
Convergence rates of efficient global optimization algorithms
Adam D. Bull
TL;DR
The paper studies how expected improvement can efficiently minimize an unknown function while providing theoretical convergence guarantees. It derives rates for fixed Gaussian-process priors, modifies the algorithm for smoother functions, and investigates data-estimated parameters. The main result is that estimated parameters can prevent convergence for standard estimators, whereas alternative estimators retain fixed-prior rates.
Problem
Expected improvement performs well experimentally, but its convergence properties are not well understood, especially when Gaussian-process prior parameters are estimated from data.
Method
The paper bounds expected-improvement convergence rates in the prior's RKHS, modifies the algorithm for smoother functions, and proposes alternative parameter estimators.
Results
O*(n^−(ν∧1)/d) convergence holds for feasible expected improvement on all f ∈ H, while a modification achieves O*(n^−ν/d); standard estimated-parameter priors may not converge.
Takeaways & Limitations
Expected improvement's guarantees depend on how its prior is specified: suitable estimators can retain fixed-prior convergence rates, whereas standard estimators can fail to discover the minimum.
Takeaways & Limitations
Uniform convergence over RKHS balls cannot be proved because the rate depends on an unbounded ratio R/R̂n.
Abstract
from arXiv · showhide
Efficient global optimization is the problem of minimizing an unknown function f, using as few evaluations f(x) as possible. It can be considered as a continuum-armed bandit problem, with noiseless data and simple regret. Expected improvement is perhaps the most popular method for solving this problem; the algorithm performs well in experiments, but little is known about its theoretical properties. Implementing expected improvement requires a choice of Gaussian process prior, which determines an associated space of functions, its reproducing-kernel Hilbert space (RKHS). When the prior is fixed, expected improvement is known to converge on the minimum of any function in the RKHS. We begin by providing convergence rates for this procedure. The rates are optimal for functions of low smoothness, and we modify the algorithm to attain optimal rates for smoother functions. For practitioners, however, these results are somewhat misleading. Priors are typically not held fixed, but depend on parameters estimated from the data. For standard estimators, we show this procedure may never discover the minimum of f. We then propose alternative estimators, chosen to minimize the constants in the rate of convergence, and show these estimators retain the convergence rates of a fixed prior.
1 Introduction
Efficient global optimization seeks a global minimum of an expensive, poorly understood function with as few evaluations as possible. The paper analyzes expected improvement, derives convergence rates, and examines the consequences of estimating prior parameters from data.
- Problem: Efficient global optimization minimizes an expensive continuous function over a compact domain without assuming convexity or unimodality.The setting includes noiseless observations and a goal of minimizing simple regret.
- Problem: Exploration and exploitation must be balanced: exploiting low-valued regions can find the optimum quickly, but insufficient exploration may miss it entirely.
- Expected improvement: Expected improvement performs well experimentally, but its theoretical behavior depends crucially on the chosen Gaussian process prior and its RKHS.
- Results: O*(n^−(ν∧1)/d) is the feasible expected-improvement rate on all f ∈ H for a prior of smoothness ν.The paper also reports O*(n^−(ν∧0.5)/d) for a computationally infeasible version on functions drawn from the prior.
- Results: O*(n^−ν/d) is achieved by a modification of expected improvement, attaining a near-optimal rate for smoother functions.
- Estimated parameters: Estimated prior parameters can fundamentally change convergence: for standard priors, smooth functions exist on which expected improvement does not converge.The paper proposes alternative estimators that minimize convergence-rate constants while retaining fixed-prior rates.
2 Expected Improvement
Expected improvement is formulated as a myopic Bayesian strategy built from a Gaussian-process model. The algorithm chooses new points using expected improvement, with kernel parameters controlling the modeled function's local behavior and scale.
- Algorithm: Expected improvement uses a myopic strategy that chooses the next observation as if optimization will stop after that observation.This simplifies computation but is suboptimal relative to the full multi-step decision problem.
- Algorithm: At each step, the algorithm selects xn+1 to maximize expected improvement over the current best observed loss.The positive-part operation x+ = max(x, 0) appears in the expected-improvement expression.
- Gaussian process model: A stationary Gaussian process models f, with σ governing global variation and Kθ governing local properties through length-scales θ.The kernel is parameterized by rescaling coordinates by their corresponding length-scales.
- Gaussian process model: The kernel smoothness parameter ν controls the regularity of prior functions, whose continuous derivatives exist almost surely up to orders k < ν.Matérn and Gaussian kernels cover smoothness levels from 0 < ν ≤ ∞.
- Algorithm: The strategy begins with initial design points chosen independently of f, then selects later points from expected-improvement maximizers.
- Parameter choice: Fixing σ and θ requires prior knowledge of f's characteristic scales and makes expected improvement behave differently under rescaling.The paper therefore motivates parameter choices that adapt automatically to the function's scale.
3 Convergence Rates
The paper analyzes expected improvement through RKHS smoothness classes, establishes convergence rates for fixed parameters, and examines how parameter estimation affects convergence. It also develops parameter choices and randomized modifications intended to preserve or improve these rates.
- 3.1 Reproducing-Kernel Hilbert Spaces: RKHSs provide the smoothness classes used to analyze expected-improvement convergence and are closely related to Sobolev spaces.For finite ν, the RKHS is equivalent to a Sobolev space of order ν+d/2; for ν = ∞, it is continuously embedded in every Sobolev space.
- 3.2 Fixed Parameters: A naive quasi-uniform design achieves the upper bound but ignores observed data and may be outperformed in practice by data-adaptive strategies.The design points are fixed in advance, while the estimated minimum is obtained by minimizing a radial basis function interpolant.
- 3.2 Fixed Parameters: The fixed-prior EI(π) strategy converges at least at rate n^−(ν∧1)/d, up to logarithmic factors.The rate applies to functions in the relevant RKHS, with the stated framework requiring convergence uniformly over bounded RKHS balls.
- 3.2 Fixed Parameters: For ν ≤ 1, the convergence rates are near-optimal, while smoother cases ν > 1 require a more difficult analysis.The paper also states that the rate can be achieved by a strategy not depending on the RKHS-radius bound R.
- 3.3 Estimated Parameters: Maximum-likelihood parameter estimation can make expected improvement never converge, even though fixed parameter choices have convergence guarantees.The paper extends this failure to standard priors with estimated parameters and constructs smooth functions on which convergence does not occur.
- 3.3 Estimated Parameters: Alternative parameter estimators minimize convergence-rate constants and retain the rates of a fixed prior, subject to exploration conditions for constant functions.The strategy requires design points to be almost surely dense in X when the observed function values are constant.
- 3.4 Near-Optimal Rates: ε-greedy modifications use random exploration to improve worst-case rates while combining global search with inference about f.The paper states that these strategies achieve near-optimal rates for all finite ν, but the result does not generally hold when ε = 1.
4 Conclusions
The paper finds that expected improvement can converge near-optimally, but naive implementations may fail to converge. It also highlights limitations of Bayesian formulations, cumulative-regret analyses, local convergence guarantees, and smoothness adaptation.
- Expected improvement can converge near-optimally, but a naive implementation may not converge at all.
- Bayesian formulations can be restrictive because placing too much faith in the prior may exclude functions of interest.
- Cumulative regret cannot establish optimization rates faster than n^-1 because it is necessarily increasing.
- Rates based on finitely many minima hold only after finding a basin of attraction, measuring local rather than global performance.
- Automatic smoothness adaptation requires estimated length-scales to tend to 0, creating practical and theoretical challenges.
A Proofs
This appendix begins the proofs of the paper’s theoretical results.
- The appendix introduces the proofs supporting the results in Section 3.
- Its purpose is to establish the paper’s theoretical convergence results.
- The proof material follows the development of the results presented earlier in the paper.
A.1 Reproducing-Kernel Hilbert Spaces
The appendix characterizes Gaussian-process RKHSs through Fourier and Sobolev spaces, then derives how these spaces change with kernel parameters.
- Fourier characterization: Fourier-transform arguments identify the RKHS on R^d with a complete function space satisfying the reproducing property.
- Sobolev equivalence: For finite ν, the RKHS associated with the kernel is equivalent to the Sobolev space H^(ν+d/2)(R^d).
- Sobolev equivalence: On Lipschitz domains, restricting the ambient RKHS yields an equivalent Sobolev space on the domain.
- Infinite smoothness: When ν = ∞, the RKHS is continuously embedded in every Sobolev space H^s(D).
- Parameter dependence: Increasing the parameter preserves membership in a related RKHS, while decreasing it preserves membership for all 0 < θ′ ≤ θ.
A.2 Fixed Parameters
The fixed-parameter analysis establishes convergence rates by combining minimax lower bounds, quasi-uniform designs, interpolation error bounds, and expected-improvement control.
- Lower bound: With n observations, disjoint-support constructions yield a lower bound because the strategy cannot distinguish among all candidate functions.
- Upper bound: A quasi-uniform, observation-independent design has fill distance h_n = O(n^-1/d), enabling radial-basis interpolation error bounds.
- Upper bound: The optimization loss is bounded by the uniform interpolation error when the interpolant’s minimizer is selected.
- Variance control: Posterior variance is controlled by distance to the nearest design point, while bounded domains limit how often new points remain far from earlier observations.
- Expected improvement: Expected improvement is bounded using the RKHS norm and posterior uncertainty when f belongs to the RKHS.
- Convergence: At selected times n_k, expected improvement forces f(x_nk+1) close to min f, producing the stated convergence-rate argument.
A.3 Estimated Parameters
The analysis shows that expected improvement with estimated parameters can avoid a region indefinitely, allowing indistinguishable functions with different minima. The proof also controls estimated parameters to recover convergence under suitable conditions.
- Proof strategy: The estimated-parameter analysis first establishes lower bounds on posterior variance and then bounds expected improvement using the estimated prior.These steps support the contradiction showing that points in V1 cannot be selected indefinitely.
- Failure with estimated parameters: Estimated-parameter expected improvement can fail to observe an open region W, so it cannot distinguish functions that differ only inside W.The constructed functions f and g agree outside W but have different minima.
- Scope of the counterexample: The counterexample can be rescaled so that its RKHS norm satisfies ∥g∥Hθ(X) ≤ R while preserving the failure for some δ > 0.This uses invariance of expected improvement under rescaling.
A.4 Near-Optimal Rates
The near-optimal-rate analysis combines quasi-uniform random exploration with expected-improvement selections to control posterior variance and obtain convergence rates. The resulting bound is uniform over functions in the specified RKHS ball.
- Random exploration: Quasi-uniform points make the mesh norm small, because partitioning X into regions of size O(n^−1/d) ensures every region is sampled with high probability.The argument uses random uniform points and concentration bounds.
- Rate mechanism: Expected improvement selects points whose function values approach the minimum when posterior variances are controlled by quasi-uniform sampling.The proof identifies selected times at which expected improvement is small, implying f(x_n) is close to min f.
- Rate bound: The analysis sets r_n = (n/log n)^−ν/d(log n)^α and uses it to bound optimization error for functions with ∥f∥HθU(X) ≤ R.The bound is derived on events combining random exploration, expected-improvement selection, and a small mesh norm.
- Uniformity and smoothness: The resulting convergence bound holds uniformly over f with ∥f∥HθU(X) ≤ R, with a constant independent of f.The same argument extends to ν = ∞ by applying the finite-ν result for every finite ν.
- Uniformity and smoothness: The constant in the rate depends only on X, K, C, θL, and θU, rather than on the particular function f.For α > 0, the same type of result follows by a similar argument.