6
$\begingroup$

I have a minimisation problem in which the parameters are a mix of integers and scalars. Some of the integers have a small range, around 0-10 but others range in the thousands. To give some context, these are all hyper-parameters of machine learning algorithms. At each iteration for a given set of parameters a series of CV and/or bootstrap tests are done to assess the merit of the parameter set.

Currently I am doing this using standard canned minimisation algorithms (specifically Nelder-Mead simplex) and faking the integer variables as continuous by doing two iterations for each value, one with the floor and the other the ceiling of the continuous value and linearly interpolating. It's crude and inefficient but at seems to at least 'work' in that the algorithm converges, eventually.

As you can imagine, the merit function iterations are expensive, so I don't want to be as wasteful as this process requires. I don't know of a standard way to deal with this kind of problem, but I can't imagine that it hasn't been addressed. Are there well known algorithms and implementations for this kind of problem?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ What function are you trying to minimize? If it is linear in the parameters, you should look into Mixed Integer LPs: en.wikipedia.org/wiki/Linear_programming#Integer_unknowns $\endgroup$
    – Mathias
    Apr 28, 2012 at 17:57
  • $\begingroup$ As stated the parameters are hyper-parameters of machine learning algorithms, so the 'function' is completlly non-analytic, and certainly not linear. $\endgroup$
    – Bogdanovist
    Apr 29, 2012 at 12:22
  • $\begingroup$ Re-reading the last comment it comes across as a bit curt. That was unintentional. To clarify in more detail, the 'function' that is being optimised is a complex process and there is no hope of using a simplifying assumptions about the response. Essentially what is needed is an algorithm that will work when the function is a black box. Nelder-Mead simplex is what I usually use in a such a situation, but that operates on continuous variables only. $\endgroup$
    – Bogdanovist
    Apr 30, 2012 at 3:03
  • $\begingroup$ No offense taken, but I appreciate the courtesy! Not being familiar with machine learning, I had no idea how the objective function to be minimized looks like. $\endgroup$
    – Mathias
    Apr 30, 2012 at 4:45

1 Answer 1

Reset to default
3
$\begingroup$

It sounds like you need a derivative free method (since it seems you can't supply a gradient for your objective function). I guess your parameter space is not bounded since you are currently using Nelder-Mead. I'm not sure what software you're using but you should check out NOMAD which is "freely distributed under the GNU Lesser General Public License." NOMAD handles nonlinear functions of integers and/or real variables. In R the crs package provides an interface, see this.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You are correct, although some of the parameters are bounded which I faked up by artificially imposing large increases in the objective function value as a function of how far out of bound a value was. Very inefficient, but it work(ed)(s). I'll take a look at NOMAD, thanks. $\endgroup$
    – Bogdanovist
    Mar 11, 2013 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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