Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Gradient descent and many other methods are useful for finding local minima in cost functions. They can be efficient when the cost function is 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 better way already available.

So my question(s) 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?

share|improve this question
2  
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 at 10:06
3  
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 at 22:45
2  
... 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 at 22:47
1  
@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 at 1:52
2  
"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. – Oxinabox Feb 1 at 8:55
up vote 24 down vote accepted

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.

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

share|improve this answer
1  
It doesn't seem to like your whole link as a direct link (I think the $ is causing it to not work right) but copypasting the whole link seems to work just fine. In any case if you click it it gives you a link to download from (which for some people is actually better) – Glen_b Jan 31 at 6:18
    
@Glen_b That's what I get for being absent-minded... Thanks! – General Abrial Jan 31 at 6:18
    
I wouldn't even suggest you fix it. Just noting for later readers who may be confused by its appearance. – Glen_b Jan 31 at 6:19
up vote 18 down vote
+100

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). user777 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).

share|improve this answer
2  
+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? – General Abrial Feb 1 at 18:33
    
The Bayesian optimization papers are quite helpful. Thank you for answering. – Jared Becksfort Feb 1 at 18:55
1  
@user777: Good point. Added an explicit reference list at the end which should be enough to recover the papers. – lacerbi Feb 1 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.

share|improve this answer
    
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. – General Abrial 4 hours ago

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.
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
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 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 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. – General Abrial 4 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.