0
$\begingroup$

Here is the URL: https://github.com/avaneev/biteopt

I've tested it on numerous global optimization benchmarking functions (included), and on real-world hyperparameter optimization problems I have. Seems to be working quite well except in comparison to deterministic methods it's necessary to make several attempts at different random seeds, so the iteration budget may be high. But stochasticity of this method gives a chance to solve a problem which can't be sufficiently solved by deterministic methods. Anyway, most benchmarking functions solve in 1 attempt given enough iteration budget.

Works best for non-convex problems, and can also solve convex problems, but of course slower than deterministic methods. Can also solve non-linear constrained problems, but such constraints increase convergence time considerably (though, this application was not tested thoroughly).

Still working on the method.

I would like to hear comments from users that have some practical models (e.g. black-box hyperparameter optimization) which are still needed to be solved acceptably - whether this method works or not for their models, possibly with the description of the model.

Here is the description of the method. The algorithm consists of the following elements:

  1. A cost-ordered population of previous solutions is maintained. A solution is an independent parameter vector which is evolved towards a better solution. On every iteration, the best solution is evolved. $$x_\text{new}=x_\text{best}$$ Below, i is either equal to rand(1, N) or in the range [1; N], depending on the AllpProb probability. Probabilities are defined in the range [0; 1] and in many instances in the code were replaced with simple resetting counters for more efficiency. Parameter values are internally normalized to [0; 1] range and, to stay in this range, are wrapped in a special manner before each function evaluation. Algorithm's hyper-parameters (probabilities) were pre-selected and should not be changed.

  2. Depending on the RandProb probability, a single (or all) parameter value randomization is performed using "bitmask inversion" operation. $$mask= 2^{1+\lfloor(0.999999997-rand(0\ldots1)^4 )\cdot MantSize\rfloor}-1$$ $$MantMult=2^{MantSize}$$ $$x_\text{new}[i] = \frac{\lfloor x_\text{new}[i]\cdot MantMult \rfloor \bigotimes mask }{MantMult}$$ Plus, with CentProb probability the random "step in the right direction" operation is performed using the centroid vector, twice. $$m_1=\text{rand}(0\ldots1)\cdot CentSpan$$ $$x_\text{new}[i]=x_\text{new}[i]-m_1(x_\text{new}[i]-x_\text{cent}[i])$$ $$m_2=\text{rand}(0\ldots1)\cdot CentSpan$$ $$x_\text{new}[i]=x_\text{new}[i]-m_2(x_\text{new}[i]-x_\text{cent}[i])$$ With RandProb2 probability an alternative randomization method is used. $$x_\text{new}[i]=x_\text{new}[i]+(-1)^{s}(x_\text{cent}[i]-x_\text{new}[i]), \quad i=1,\ldots,N,\\ \quad s\in\{1,2\}=(\text{rand}(0\ldots1)<0.5 ? 1:2)$$

  3. (Not together with N.2) the "step in the right direction" operation is performed using the random previous solution, current best and worst solutions. This is conceptually similar to Differential Evolution's "mutation" operation. $$x_\text{new}=x_\text{best}-\frac{(x_\text{worst}-x_\text{rand})}{2}$$

  4. With ScutProb probability a "short-cut" parameter vector change operation is performed. $$z=x_\text{new}[\text{rand}(1,N)]$$ $$x_\text{new}[i]=z, \quad i=1,\ldots,N$$

  5. After each objective function evaluation, the highest-cost previous solution is replaced using the cost constraint.

You can find this algorithm implemented in the optimize() function in biteopt.h on lines 284-395, it does not involve any higher-order math.

$\endgroup$
  • 11
    $\begingroup$ While this might be an interesting method, the post does not feature any technical detail about it. The mentioned GitHub page contains more; however, I still do not see a clean mathematical description of what is happening inside. I would recommend including the necessary technical details to this post, as well as a more concrete question because a request for comments is not aligned well with how CompSci SE works. $\endgroup$ – Anton Menshov Apr 24 '18 at 16:34
  • 3
    $\begingroup$ This question could arguably be more appropriate for Code Review if you were just looking for comments about the code quality and structure. If you were to, say, post an example problem here and some benchmarks of how your code does, others might be able to offer some feedback on how it stacks up against other methods or implementations. $\endgroup$ – Daniel Shapero Apr 24 '18 at 17:53
  • 6
    $\begingroup$ I'm 20 years in commercial software production, no need for code review. I disagree - code review is always useful, even for seasoned programmers $\endgroup$ – GoHokies Apr 25 '18 at 7:15
  • 2
    $\begingroup$ I think it is not so helpful to advise writing up as a scientific paper. Other than altruism for the scientific community this has little value outside academia. The author is asking for a bit of advice and input on the method is this causal forum. I have asked many questions here before on mathematical methods and never encountered this disappointing attitudes. Personally I think this question poses a reasonable request and is appropriate for this site provided the post includes sufficient technical information on the method. $\endgroup$ – boyfarrell Apr 25 '18 at 15:49
  • 1
    $\begingroup$ To put it briefly, there needs to be some parity between the amount of effort put into addressing an audience (whether it be users of this site or peer reviewers for a journal) and the amount of effort on your behalf you can expect from them in return. And my feeling is that this is missing here (but not in @boyfarrell's questions, for example). It is even worse if -- as it seems from aleksv' comment -- you are looking for commercial evaluation, where you are asking others to do part of the work (market assessment) for free... $\endgroup$ – Christian Clason Apr 25 '18 at 16:48
6
$\begingroup$

I would like to hear comments from users that have some practical models (e.g. black-box hyperparameter optimization) which are still needed to be solved acceptably - whether this method works or not for their models, possibly with the description of the model.

Looks like you want somebody to invest what may be considerable time and energy in trying out your new method on their models, and report on the results.

As a modeler, I have to ask myself the question: why would I do that? It'd take me some time to change my code and link in your method. What does your optimization method have to offer that may be better than my current method of choice? Now, we can't possibly answer this question because (a) you don't know what models I'm working with, and (b) I don't know what kind of problems your method is good for - beyond some "real-life optimization problems" where it "seems to be working quite well".

Bottom line is you have to do a heck of a better job "selling" your method to the community at large. You could start by:

  • testing the method on a representative sample of problems where you expect it to do well, and report on the results;
  • compare the results with those achieved by similar, known methods (to show us that you're at least competitive with the state of the art);
  • show that your method converges, and under which conditions - if you can't come up with a formal proof, then at least give some heuristic arguments (backed up by some solid experimental data);
  • advise on the choice of hyper-parameters, like RandProb, CentProb, etc.
  • tell us what problems we should not be using your method on, and why.
$\endgroup$
  • 3
    $\begingroup$ ...which is a pretty good description of a typical publication in the field of optimization :) $\endgroup$ – Christian Clason Apr 25 '18 at 19:37
  • $\begingroup$ Thanks for the comment. Optimization field is sparse. Will you buy someone's own benchmarks? I would not, I've studied optimization enough to not believe in "published results" since they are in most cases biased. Then my problems of choice are not your problems of choice. It would be more useful if you actually included problems you are interested in solving, I may check them out. Not sure I understand your notion of "investing a lot of time". The example provided is as simple as it can be, only 5 minutes of time to download, study and print "gcc example.cpp". $\endgroup$ – aleksv Apr 25 '18 at 19:55
  • $\begingroup$ I did comparisons and included results on the project page - but as I've expected, you are not buying it. What can I do more? $\endgroup$ – aleksv Apr 25 '18 at 19:58
  • $\begingroup$ Hyperparameters should not be changed. I've mentioned problems my method should not be used on - problems with multiple minima without detectable global descent (Bukin 6), problems with rogue optimums (Damavandi), combinatorial problems (Lennard-Jones and Perm problems). $\endgroup$ – aleksv Apr 25 '18 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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