# Optimization when Cost Function Slow to Evaluate

Gradient descent and many other methods are useful for finding local minima in cost functions. They can be efficient when the cost function can be evaluated quickly at each point, whether numerically or analytically.

I have what appears to me to be an unusual situation. Each evaluation of my cost function is expensive. I am attempting to find a set of parameters that minimize a 3D surface against ground truth surfaces. Whenever I change a parameter, I need to run the algorithm against the entire sample cohort to measure its effect. In order to calculate a gradient, I need to change all 15 parameters independently, meaning I have to regenerate all the surfaces and compare against the sample cohort way too many times per gradient, and definitely way too many times over the course of optimization.

I have developed a method to circumvent this problem and am currently evaluating it, but I am surprised that I have not found much in the literature regarding expensive cost function evaluations. This makes me wonder if I am making the problem harder than it is and that there might be a better way already available.

So my questions are basically this: Does anyone know of methods for optimizing cost functions, convex or not, when evaluation is slow? Or, am I doing something silly in the first place by rerunning the algorithm and comparing against the sample cohort so many times?

• Have you heard of stochastic gradient descent? For deep neural networks applied to large Training sets you have a similar issue (but can Eval gradient analytically) and the standard solution is to make gradient descent based only on a single sample(stochastic) vs the whole cohort (batch) – seanv507 Jan 31 '16 at 10:06
• I'm only vaguely familiar with the area, so hence this being a comment rather than an answer. But what you are discussing sounds a lot like the topic of Uncertainty Quantification, often faced by engineers, where a single evaluation of the target function made take weeks to evaluate (at least in the problems faced by my engineering coworkers). My very limited understanding of how this is handled is by making a surrogate approximation that is much easier to evaluate based on past evaluations and simpler engineering models and then use these surrogate models to chose the next evaluation... – Cliff AB Jan 31 '16 at 22:45
• ... of the more expensive target function. I hate to say it, but I don't know anymore about the topic at the moment; I've only been told about it briefly while discussing research topics with said engineers. Interestingly, it seems like a very challenging research area: I believe good models require both a good understanding of the physics and statistics. – Cliff AB Jan 31 '16 at 22:47
• @seanv507 Yes, thanks, but I avoided it for a similar reason. It takes about 30 seconds to a minute to run one sample. If I have 15 parameters, I am looking at nearly 8 minutes per gradient calculation even if I only use one sample. If the space is large, it may take a very long time. Please correct me if you had other ideas in mind. – Jared Becksfort Feb 1 '16 at 1:52
• "what appears to me to be an unusual situation. Each evaluation of my cost function is expensive.". This is not at all an unusual situation, in general. It shows up all over the place, for example when ever your cost function comes from running a simulation (Eg in this paper: white.ucc.asn.au/publications/White2015PsoTransistorSizing.pdf we simulate a circuit in SPICE taking 10s). More boardly, in experimental science, evaluations can take ages. One of my friends Masters project is basically optimizing 5 parameters to find the best way of inserting DNA. Each evaluation takes 24 hours. – Lyndon White Feb 1 '16 at 8:55

# TL;DR

I recommend using LIPO. It is provably correct and provably better than pure random search (PRS). It is also extremely simple to implement, and has no hyperparameters. I have not conducted an analysis that compares LIPO to BO, but my expectation is that the simplicity and efficiency of LIPO imply that it will out-perform BO.

# Bayesian Optimization

Bayesian Optimization-type methods build Gaussian process surrogate models to explore the parameter space. The main idea is that parameter tuples that are closer together will have similar function values, so the assumption of a co-variance structure among points allows the algorithm to make educated guesses about what best parameter tuple is most worthwhile to try next. This strategy helps to reduce the number of function evaluations; in fact, the motivation of BO methods is to keep the number of function evaluations as low as possible while "using the whole buffalo" to make good guesses about what point to test next. There are different figures of merit (expected improvement, expected quantile improvement, probability of improvement...) which are used to compare points to visit next.

Contrast this to something like a grid search, which will never use any information from its previous function evaluations to inform where to go next.

Incidentally, this is also a powerful global optimization technique, and as such makes no assumptions about the convexity of the surface. Additionally, if the function is stochastic (say, evaluations have some inherent random noise), this can be directly accounted for in the GP model.

On the other hand, you'll have to fit at least one GP at every iteration (or several, picking the "best", or averaging over alternatives, or fully Bayesian methods). Then, the model is used to make (probably thousands) of predictions, usually in the form of multistart local optimization, with the observation that it's much cheaper to evaluate the GP prediction function than the function under optimization. But even with this computational overhead, it tends to be the case that even nonconvex functions can be optimized with a relatively small number of function calls.

A widely-cited paper on the topic is Jones et al, "Efficient Global Optimization of Expensive Black-Box Functions." But there are many variations on this idea.

# Random Search

Even when the cost function is expensive to evaluate, random search can still be useful. Random search is dirt-simple to implement. The only choice for a researcher to make is setting the the probability $p$ that you want your results to lie in some quantile $q$; the rest proceeds automatically using results from basic probability.

Suppose your quantile is $q = 0.95$ and you want a $p=0.95$ probability that the model results are in top $100\times (1-q)=5$ percent of all hyperparameter tuples. The probability that all $n$ attempted tuples are not in that window is $q^n = 0.95^n$ (because they are chosen independently at random from the same distribution), so the probability that at least one tuple is in that region is $1 - 0.95^n$. Putting it all together, we have

$$1 - q^n \ge p \implies n \ge \frac{\log(1 - p)}{\log(q)}$$

which in our specific case yields $n \ge 59$.

This result is why most people recommend $n=60$ attempted tuples for random search. It's worth noting that $n=60$ is comparable to the number of experiments required to get good results with Gaussian Process-based methods when there are a moderate number of parameters. Unlike Gaussian Processes, the number of queries tuples does not change with the number of hyperparameters to search over; indeed, for a large number of hyperparameters, a Gaussian process-based method can take many iterations to make headway.

Since you have a probabilistic guarantee of how good the results are, it can be a persuasive tool to convince your boss that it's not necessary to run more experiments.

# LIPO and its Variants

This is an exciting arrival which, if it is not new, is certainly new to me. It proceeds by alternating between placing informed bounds on the function, and sampling from the best bound, and using quadratic approximations. I'm still working through all the details, but I think this is very promising. This is a nice blog write-up, and the paper is Cédric Malherbe and Nicolas Vayatis "Global optimization of Lipschitz functions."

• This seems like a modern variant of response surface methods! – kjetil b halvorsen May 16 '17 at 17:06
• Actually, random search can work remarkably well: argmin.net/2016/06/20/hypertuning – Tim Jun 21 '18 at 15:09
• @Tim Yes, your point is well-taken. I didn't want to "decide" the issue of which is better in this post, since there are essentially endless permutations on BO, each claiming to be "the best" black-box optimizer -- making it impossible to be definitive. I agree that random search can work quite well, but I would actually recommend LIPO over PRS. LIPO is provably correct and strongly out-performs PRS (on average) in all of my experiments. LIPO also has minimal estimation cost: if you can minimize a QP, then you can use LIPO, and LIPO has zero hyperparameters (in contrast to BO). – Sycorax Jun 21 '18 at 15:14
• I am glad I checked this question out again. LIPO seems great. – Jared Becksfort Jan 9 at 21:12
• LIPO is great. When I have a moment I'll expand my answer to give a better accounting of LIPO. – Sycorax Jan 9 at 22:02

The literature on evaluation of expensive black-box function is quite vast and it is usually based on surrogate-model methods, as other people pointed out. Black-box here means that little is known about the underlying function, the only thing you can do is evaluate $f(x)$ at a chosen point $x$ (gradients are usually not available).

I would say that the current gold standard for evaluation of (very) costly black-box function is (global) Bayesian optimization (BO). Sycorax already described some features of BO, so I am just adding some information that might be useful.

As a starting point, you might want to read this overview paper 1. There is also a more recent one [2].

Bayesian optimization has been growing steadily as a field in the recent years, with a series of dedicated workshops (e.g., BayesOpt, and check out these videos from the Sheffield workshop on BO), since it has very practical applications in machine learning, such as for optimizing hyper-parameters of ML algorithms -- see e.g. this paper [3] and related toolbox, SpearMint. There are many other packages in various languages that implement various kinds of Bayesian optimization algorithms.

As I mentioned, the underlying requirement is that each function evaluation is very costly, so that the BO-related computations add a negligible overhead. To give a ballpark, BO can be definitely helpful if your function evaluates in a time of the order of minutes or more. You can also apply it for quicker computations (e.g. tens of seconds), but depending on which algorithm you use you may have to adopt various approximations. If your function evaluates in the time scale of seconds, I think you're hitting the boundaries of current research and perhaps other methods might become more useful. Also, I have to say, BO is rarely truly black-box and you often have to tweak the algorithms, sometimes a lot, to make it work at full potential with a specific real-world problem.

BO aside, for a review of general derivative-free optimization methods you can have a look at this review [4] and check for algorithms that have good properties of quick convergence. For example, Multi-level Coordinate Search (MCS) usually converges very quickly to a neighbourhood of a minimum (not always the global minimum, of course). MCS is thought for global optimization, but you can make it local by setting appropriate bound constraints.

Finally, you are interested in BO for target functions that are both costly and noisy, see my answer to this question.

References:

1 Brochu et al., "A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning" (2010).

[2] Shahriari et al., "Taking the Human Out of the Loop: A Review of Bayesian Optimization" (2015).

[3] Snoek et al., "Practical Bayesian Optimization of Machine Learning Algorithms", NIPS (2012).

[4] Rios and Sahinidis, "Derivative-free optimization: a review of algorithms and comparison of software implementations", Journal of Global Optimization (2013).

• +1 This is a great answer. In particular, these papers are a great addition to this thread; indeed, I didn't know that the general method I described is called Bayesian Optimization. But I'm concerned that the links may go bad over time. Would you mind adding more complete citation information so that future users will be able to access these papers? – Sycorax Feb 1 '16 at 18:33
• The Bayesian optimization papers are quite helpful. Thank you for answering. – Jared Becksfort Feb 1 '16 at 18:55
• @user777: Good point. Added an explicit reference list at the end which should be enough to recover the papers. – lacerbi Feb 1 '16 at 19:14

I don't know the algorithms myself, but I believe the kind of optimization algorithm that you are looking for is derivative-free optimization, which is used when the objective is costly or noisy.

For example, take a look at this paper (DOI 10.1023/A:1011584207202) whose abstract seems to indicate this is exactly what you want:

The paper considers global optimization of costly objective functions, i.e. the problem of finding the global minimum when there are several local minima and each function value takes considerable CPU time to compute. Such problems often arise in industrial and financial applications, where a function value could be a result of a time-consuming computer simulation or optimization. Derivatives are most often hard to obtain, and the algorithms presented make no use of such information.

• Please include full citation information for the linked papers and other resources. We want to build a durable repository of information, and links tend to go bad over time. – Sycorax May 27 '16 at 13:59
• Björkman, M. & Holmström, K. "Global Optimization of Costly Nonconvex Functions Using Radial Basis Functions." Optimization and Engineering (2000) 1: 373. doi:10.1023/A:1011584207202 – jkdev Jan 31 '17 at 17:32

You are not alone.

Expensive-to-evaluate systems are very common in engineering, such as finite element method (FEM) models and computational fluid dynamics (CFD) models. Optimization of these computatationaly expensive models is very needed and challenge because evoluationary algorithms often needs tens of thouands of evaluations of the problem which is not an option for expensive-to-evaluate problems. Fortunately, there are lots of methods (algorithms) avaiable to solve this problem. As far as I know, most of them are based on surrogate models (metamodels). Some are listed below.

• Efficient Global Optimization (EGO) [1]. The EGO algorithm has been mentioned above and may be the most famous surrogate-based optimization algorithm. It is based on the Kriging model and an infill criterion called expected improvement function (EI). R packages including the EGO algorithm are DiceOptim and DiceKriging.
• Mode-pursuing sampling (MPS) method [2]. The MPS algorithm is built on the RBF model and an adptive sampling strategy is used to pick up candidate points. The MATLAB code is publised by the authors at http://www.sfu.ca/~gwa5/software.html. The MPS algorithm may need more evaluations to get the optimum, but can handle more complicated probelms than the EGO algorithm from my personal experience.
• Ensemble surrogates models by Juliane Müller [3]. She used multiple surrogates to enhance the searching ability. The MATLAB toolbox MATSuMoTo is avaiable at https://github.com/Piiloblondie/MATSuMoTo.

In summery, these surrogate-based optimization algorithms try to find the global optimum of the problem using as few evaluations as possible. This is achieved by making the full use of the informations that the surrogate (surrogates) provides. Reviews on optimization of compuationally expensive problems are in [4-6].

Reference:

1. D. R. Jones, M. Schonlau, and W. J. Welch, "Efficient global optimization of expensive black-box functions," Journal of Global Optimization, vol. 13, pp. 455-492, 1998.
2. L. Wang, S. Shan, and G. G. Wang, "Mode-pursuing sampling method for global optimization on expensive black-box functions," Engineering Optimization, vol. 36, pp. 419-438, 2004.
3. J. Müller, "Surrogate Model Algorithms for Computationally Expensive Black-Box Global Optimization Problems," Tampere University of Technology, 2012.
4. G. G. Wang and S. Shan, "Review of metamodeling techniques in support of engineering design optimization," Journal of Mechanical Design, vol. 129, pp. 370-380, 2007.
5. A. I. Forrester and A. J. Keane, "Recent advances in surrogate-based optimization," Progress in Aerospace Sciences, vol. 45, pp. 50-79, 2009.
6. F. A. C. Viana, T. W. Simpson, V. Balabanov, and V. Toropov, "Metamodeling in Multidisciplinary Design Optimization: How Far Have We Really Come?," AIAA Journal, vol. 52, pp. 670-690, 2014/04/01 2014.

The two simple strategies that I have successfully used in the past are:

1. If possible, try to find a simpler surrogate function approximating your full cost function evaluation -- typical an analytical model replacing a simulation. Optimize this simpler function. Then validate and fine tune the resulting solution with your exact cost function.
2. If possible, try to find a way to evaluate an exact "delta-cost" function -- exact as opposed to be an approximation from using the gradient. That is, from an initial 15-dimensional point for which you have the full cost evaluated, find a way to derive how the cost would change by making a small change to one (or several) of the 15 components of your current point. You would need to exploit localization properties of a small perturbation if any in your particular case and you would likely need to define, cache, and update an internal state variable along the way.

Those strategies are very case specific, I don't know whether they can be applicable in your case or not, sorry if they are not. Both could be applicable (as it was in my use cases): apply the "delta-cost" strategy to a simpler analytical model -- performance may improve by several orders of magnitudes.

Another strategy would be to use a second order method that typically tends to reduce the number of iterations (but each iteration is more complex) -- e.g., Levenberg–Marquardt algorithm. But considering you don't seem to have a way to directly and efficiently evaluate the gradient, this is probably not a viable option in this case.

As other people mentioned, a surrogate model (also called response surface) is a powerful approach. In my opinion, one crucial thing people forget is that you can perform several function evaluations in parallel, if using multicore CPUs.

I'd suggest looking at this code, it uses simple response model, but scales on multicore CPUs, which gives a speedup equal to amount of cores used. A mathematics behind the method is described in this paper.

• I assume you are the first author on the paper -- you should probably mention that if it is the case. The paper lacks comparison with state-of-the-art methods such as Bayesian optimization or other surrogate methods (in fact, it does not provide any benchmark at all). Can you maybe tell something more? – lacerbi May 19 '16 at 15:41
• I'm not saying that model used there is better. I'm just saying that people are too concerned about quality of the model and sometimes forget about parallelism, which can be a big deal when many cores are involved.. – Paul May 19 '16 at 15:45
• Please include full citation information for the linked papers and other resources. We want to build a durable repository of information, and links tend to go bad over time. – Sycorax May 27 '16 at 13:59
• I am not sure how much terminology varies by community, but I commonly here response surface used as a synonym for "polynomial surrogate model" (typically a quadratic). So I tend to think of surrogate modeling as a superset of response-surface modeling. (This may be incorrect, though.) – GeoMatt22 Oct 13 '16 at 1:30

There are many tricks used in stochastic gradient descent that can be also applied to objective function evaluation. The overall idea is trying to approximate the objective function using a subset of data.

My answers in these two posts discuss why stochastic gradient descent works: the intuition behind it is to approximate the gradient using a subset of data.

How could stochastic gradient descent save time comparing to standard gradient descent?

How to run linear regression in a parallel/distributed way for big data setting?

The same trick applies to the objective function.

Let's still use linear regression as an example: suppose the objective function is $$\|Ax-b\|^2$$. If $$A$$ is huge, say a trillion rows, evaluating it once will take a very long time. We can always use a subset of $$A$$ and $$b$$ to approximate the objective function, which is the squared loss on the subset of the data.