Optimization of EI always gets stuck in local extrema

fgerzer / apsis

Other

25 stars 4 forks source link

Optimization of EI always gets stuck in local extrema #31

Closed andi1400 closed 9 years ago

andi1400 commented 9 years ago

At the moment we optimize EI with scypy.optimize.minimize. Tried several optimizer methods, all of them get stuck in local extrema.

Problem seems to be well known:

the bergstra group reports on it http://papers.nips.cc/paper/4443-algorithms-for-hyper-parameter-optimization.pdf (page 3)
http://www.icml2010.org/papers/297.pdf report about this, too
the old spearmint package also seems to use grid search here if I understand their code right

Proposed optimization methods there

grid search (probably not feasible)
evolutionary algorithm

Other ideas

random search, how many points?
continue using SLSQP, L-BFGS-B and implement a random restart for them. How often?

bayerj commented 9 years ago

Climin has a recent evolutionary algorithm. https://github.com/BRML/climin/blob/master/climin/nes.py

I say continue with grid search first, solve the problem later.

fgerzer commented 9 years ago

I agree with that. GridSearch (or random search) should suffice for now. After all, the main problem will be inverting the matrix, not evaluating it.

andi1400 commented 9 years ago

~~reminder: at the moment number of grid points for scipy.brute grid search is hard coded!~~ No its not, sorry. My fault.

andi1400 commented 9 years ago

during the work on #34 we switched to using random search as only possibility right now. Keep this in mind when going on here to reenable optimization choice.

andi1400 commented 9 years ago

@andi1400 Document about new EI optimization. Implement optimize_restarts

andi1400 commented 9 years ago

EI Opzimization Improved. We now have implemented EI gradient for use in BFGS optimization of EI. This optimization can be activated setting "acquisition_hyperparams":{"optimization": "bfgs"}.

It will work as follows:

first random search with 1000 samples is executed
the best result found in random search is used as a starting point in BFGS
if BFGS optimization is successful in can only be better than the starting point (can be theoretically proven) => this result will be reported as maximium. In case BFGS was not successful the random search result will be used.

To be done here: Add multiple restarts to BFGS. Make BFGS to be the standard optimizer. Do a bit of performance evaluation to verify results.

fgerzer commented 9 years ago

Closed with the new optimization. For details, see the commits referencing this issue.