9 ms·
Gradient Free Optimizers: A collection of modern optimization methods in Python
- morelandjs 6y agoThis looks great! You have a lot of algorithms here. Which ones do you find to be the most promising for general use and why?
- simonblanke 6y agoI think Random Restart Hill Climbing is good if your objective function evaluates fast (simple functions). It does not get stuck in local optima and also does local search very well. Bayesian Optimization is very good if your objective function takes some time (> 1 second) to evaluate. If you look at the gifs in the readme of Gradient-Free-Optimizers you will see how fast it finds promising solutions. It is almost scary how good it is (even compared to other smbo).
- morelandjs 6y agoThanks, that's useful. My impression of Bayesian parameter optimization using Gaussian processes is that it is quite good when the data has a more or less constant correlation length across the evaluation points as in your example. When there are large correlation lengths in some regions of the dataset and small correlation lengths elsewhere, it often over (or under) shoots the curvature of the hypersurface.
- protoplaid 6y agoWhich algorithm would you recommend when the objective function is noisy (and nondeterministic)? For example the objective function is the "score" of a particular stochastic simulation, which can be started with varied initial random seed, or the result of a real physical experiment, which is naturally stochastic (and expensive to evaluate). There is a tradeoff between getting a very accurate estimation of the objective function + variance of a single point vs exploring other points. Is there a search algorithm that somehow manages this tradeoff automatically? Note: In the past I've used Tree of Parzen Estimators (Kernel density estimators), wasting 3-4 evaluations per point, but I have a feeling it is sub-optimal. Is there an "optimal" algorithm, like the optimal algorithm for the multi-armed bandit problem[1] (which is similar) [1] https://en.wikipedia.org/wiki/Multi-armed_bandit https://en.wikipedia.org/wiki/Multi-armed_bandit
- morelandjs 6y agoI'm wondering the same. I'd be concerned that Random Restart Hill climbing would essentially chase random noise.
- simonblanke 6y agoYou could be right. I must confess, that i have a (probably) very narrow understanding of typical optimization problems. Most of the objective functions i optimize have machine learning algorithms in it (to optimizer hyperparameters). Depending on the evaluation those can have low noise. If you like you could provide other use cases and applications for optimization algorithms.
- plaidfuji 6y agoBayesian Optim is designed for that case specifically. It fits a surrogate model with uncertainty estimates and picks the next point with an understanding of that uncertainty. Look up the MEI acquisition function for more info. Edit: BO does usually require some tuning for your use case. Its acquisition function sometimes samples replicates where there’s high noise, especially if the first sample looks particularly “good”. There’s usually a hyper parameter that can be set to favor exploration vs exploitation, I.e. to favor non-replicate samples. But I am not aware of an algo that can learn your preference along that axis.
- protoplaid 6y agoCorrect me if I'm wrong, but it seems the bayesian_optimization.py optimizer in this library assumes that the sampled points are exact, ie their variance is zero. It doesn't seem to re-sample existing points. This will cause the algorithm to "chase random noise", as morelandjs wrote below
- plaidfuji 6y agoI would be very disappointed if that were the case.. no, it looks like it’s set up to capture variance. The BO algo wraps an “Expected Improvement Optimizer”: https://github.com/SimonBlanke/Gradient-Free-Optimizers/blob/master/gradient_free_optimizers/optimizers/sequence_model/exp_imp_based_opt.py https://github.com/SimonBlanke/Gradient-Free-Optimizers/blob... Which selects new points based on both the model’s mean estimate and its variance. See around line 58
- optimalsolver 6y agoNot OP, but you can't go wrong with randomized/stochastic hill-climbing.It's actually very competitive with complex, fancy genetic algorithms: https://core.ac.uk/download/pdf/37767541.pdf https://core.ac.uk/download/pdf/37767541.pdf
- plaidfuji 6y agoBe still my heart... could this be... the missing gradient-free optim library for Python? Particle swarm, evolutionary, AND Bayesian all in a single package? A no-nonsense, simple API with strong enough defaults that you can basically just call .search() with a function (I’m looking at you, nevergrad)?? I’ll have to test it of course but this looks truly life changing. A few clarifications, if the author happens to be watching this thread: - looks like the search space is “enumerated”, I.e. I define the grid spacing for each independent variable in search_space and it puts together an outer product? In other words, this will never be truly continuous? - by the same token, constraints are applied by virtue of specifying the endpoints of each grid in the search_space? Is it possible for me to apply more complex constraints by generating my own enumerated list of search_space points and feeding that directly? Seriously well done. Like I said above, this looks to me like an immediate staple library.
- optimalsolver 6y agoThere's also Opytimizer [0] for almost every metaheuristic optimization algorithm under the Sun. [0] https://github.com/gugarosa/opytimizer https://github.com/gugarosa/opytimizer
- simonblanke 6y agoI am glad you like my project. The search space is not continuous. But you can make the steps as small as you want. Like: np.arange(0, 10, 0.00001) I am not sure i understand your second question. The entire search space is always a N-dimensional cube. So you just define a start and end point and the step size in each dimension.
- plaidfuji 6y agoNope, that answers the question. I was asking about cases where the space is, for example, a triangle or something non-cuboidal. Think constraints like x1 + x2 < 1 or something like that. What I’m wondering is if your library converts the search_space to an enumerated list of candidate points somewhere in the backend, and if there’s a way for me to just construct that list and pass it directly for more complex cases.
- twic 6y agoI love gradient-free optimisers - there are so many interesting problems where there aren't analytical gradients available. An I right in thinking this library doesn't contain a simplex / Nelder-Mead optimiser? To me that's the bread and butter of gradient-free optimisation. Also no Powell algorithms like BOBYQA? nlopt has these and many more, and a Python wrapper: https://nlopt.readthedocs.io/en/latest/NLopt_Algorithms/ https://nlopt.readthedocs.io/en/latest/NLopt_Algorithms/ So, are those omitted because this library is modern and those are now considered out of date?
- simonblanke 6y agoI am currently working on the Nelder-Mead optimiser. I will also look into "BOBYQA". I am always searching for interesting algorithms that my users need. If you have more suggestions you can open an issue in the repository.
- twic 6y agoThat's good to hear. I don't have any other specific requests - for me it seems impossible to know what will work on my problems, so i just try things at random to see what works! I don't know the architecture of your project, but is there any way it could include NLopt, and so make all of its algorithms available? Some of them could be useful, and i doubt it's a good use of your time to reimplement them all from scratch.
- simonblanke 6y agoUnfortunately NLopt cannot be included into Gradient-Free-Optimizers. But i would like to implement multiple algorithms that are also preset in NLopt. I think it will help my understanding of optimization algorithms if i implement them myself. I currently have my eyes on the Downhill-simplex, Direct and Powell's Method. But they are quite different from what i have already implemented, so this could take some time.
- sleavey 6y agoI've used this, and it works nicely: https://github.com/numericalalgorithmsgroup/pybobyqa https://github.com/numericalalgorithmsgroup/pybobyqa. I'd be happy if it were added to your project, then I could just use yours and have access to a bunch of alternatives with the same API.
- optimalsolver 6y agoI hope to see gradient-free/black box optimization algorithms gain more popularity in machine learning. I'm always surprised when I see a review of ML optimization methods, and it's not even mentioned that you can optimize an ML model without using the gradient. Also, love or hate Python, there's almost always a library for whatever it is you want to do.
- xyzzyz 6y ago> and it's not even mentioned that you can optimize an ML model without using the gradient. Can you, though? How does the outcomes compare to gradient based methods?
- cgearhart 6y agoIn general GFO is not a good alternative when there are lots of model parameters or when it’s cheap to get the gradient. GFO could be used to train models, but kinda in the same way that you could find your way to Cleveland by just wandering around long enough. It sure would help a lot if you had a compass.
- xyzzyz 6y agoYeah, that's what I thought. For deep learning models, when your parameter space has many thousands dimensions, it's really cheap to use gradient-based methods, when you can use stochastic gradient descent and backpropagation to quickly calculate good estimates of gradient. I simply don't see why eschewing this structure can lead to anything competitive.
- simonblanke 6y agoI just saw, that my project got a lot of new stars on github. A surprise to be sure, but a welcome one.
- simonblanke 6y agoAlso: Gradient-Free-Optimizers is basically just the optimization-backend for a much larger project of mine: https://github.com/SimonBlanke/Hyperactive https://github.com/SimonBlanke/Hyperactive
- amatic 6y agoAmazing collection! I'm learning about backprop in neural networks and I'm reading how that kind of optimization may not be biologically 'implementable'. Are non-gradient based optimizers an alternative proposal for biological learning? How do they compare to backprop?
- asah 6y agoGiven the rise of multi-core machines, parallel optimization seems pretty important. Which of these support parallel execution ? For this reason, I chose Mango for a recent project: https://github.com/ARM-software/mango https://github.com/ARM-software/mango (bayesian optimizer with built-in support for both parallel optimization (via multiprocessing) and distributed (via celery))
- simonblanke 6y agoGradient-Free-Optimizers is a lightweight optimization package that serves as a backend for Hyperactive: https://github.com/SimonBlanke/Hyperactive https://github.com/SimonBlanke/Hyperactive Hyperactive can do parallel computing with multiprocessing or joblib, or a custom wrapper-function. Parallel computing can be done with all its optimization algorithms. You could even pass a gaussian process regressor like GpFlow to the Bayesian Optimizer (GFO and Hyperactive) to get GPU acceleration.
- wtallis 6y agoConsider adding some affordance for parallel computing to Gradient-Free-Optimizers by allowing the user to provide a vectorized objective function instead of one that evaluates only a single point in the search space per function call. That leaves all the hard work of parallelization as an exercise for the user, and gives the user the flexibility to parallelize their objective function with whatever mechanism they wish. I have previously used this approach in a project where the objective function contained a half-hour long simulation, which was the bottleneck that made estimating a gradient intractable. When the optimization algorithm gave a batch of several points in the search space to evaluate, our objective function could prepare and run several instances of the simulation in parallel, and return when the whole batch was complete. From this, it was easy for us to also distribute simulation runs across several machines, without needing any changes to the optimizers. We would not have been able to easily achieve this with an optimization framework that tried to directly manage parallelization, because the steps necessary to prepare the input files for the simulation software had to be done serially. For that project we tried: DIRECT, several variants of Nelder-Mead, and an evolutionary strategy. In hindsight, the Nelder-Mead variants worked best; once we accumulated enough simulation results it became clear that our objective function was convex and pretty well-behaved in the region of interest. Nelder-Mead was also trivial to extend to trying several extra points per batch to ensure that each of our several workstations had something to work on. (We didn't have access to a large cluster, and Nelder-Mead wouldn't generalize well to a large degree of parallelization in that manner.)
- mik09 6y agonice repo, i saw some comments expressing excitement and thought of the first time i saw pymoo, tpot, and finally automl. there are a lot of stuff laying around github but we just need to search better, like using topics (tags) and the gazer repo which kinda page-ranks the github repos.
- simonblanke 6y agoI had the same excitement for tpot! That project was the reason i started creating mine.
- jordigh 6y agoIs the Nelder-Mead a.k.a. the other simplex method any good? I remember most of these other methods from my optimisation lessons, but I'm surprised to not see Nelder-Mead in this list.
- simonblanke 6y agoI am currently working on the Nelder-Mead algorithm. I did not realize that it is that popular. This gives me motivation to implement it soon ;-) If there are more "must have"-algorithms you could open an issue in Gradient-Free-Optimizers.
- jordigh 6y agoI like it because it was so easy to implement and it worked well, unless your objective function had very narrow and steep valleys. I don't know if it's popular, heheh, it's been a while since I've been in maths school, so that's why I'm asking.
- morelandjs 6y agoGetting a lot of these errors when using the GPR. Seems to be an issue with the estimation of the noise level term. Scratching my head on this one. Anyone familiar with what's going on? I tried adding some random noise to the optimization function, and it had the same issue. ...python3.8/site-packages/sklearn/gaussian_process/kernels.py:402: ConvergenceWarning: The optimal value found for dimension 0 of parameter k2__noise_level is close to the specified lower bound 1e-05. Decreasing the bound and calling fit again may find a better value.
- simonblanke 6y agoYeah this is a warning from sklearns gaussian process regressor. Sklearn probably wants you to increase the "n_restarts_optimizer"-parameter of the gpr, but from my experience this warning does not correlate with bad results from Gradient-Free-Optimizers. Sklearn warnings are often difficult to silence. Just google "sklearn suppress warnings" to get a code snippet for this problem.
- morelandjs 6y agothanks!
- shankr 6y agoCan you use the methods in this library to do constrained optimization? Whenever I look for such gradient free optimizer it's always comes with some constraint.
- bbwwnn 6y agoOne simple trick is doing a bijective transformation between your constrained input space and the unconstrained optimizer space. For example, if you have x>0 in your input space, you take the input from your optimizer and apply e^x to it. Or if you have a<x<b you can do a+b*logit(x). What exactly you choose will depend on your prior on how your function behaves.
- klon 6y agoI am surprised CMA-ES is not included. It is the state of the art gradient free optimization algorithm last I checked. https://en.wikipedia.org/wiki/CMA-ES https://en.wikipedia.org/wiki/CMA-ES
- simonblanke 6y agoEvolution strategy is included. The "Covariance matrix adaptation" is for making this algorithm work for continuous search spaces. But gradient-free-optimizers has discrete search space.
- twic 6y agoFor linear programming solvers, there is an annual competition to see which is best: https://www.minizinc.org/challenge.html https://www.minizinc.org/challenge.html Is there anything like this for gradient-free optimisers?
- simonblanke 6y agoI thought about a table in the readme that shows some kind of metric for each optimizer that describes its performance. I will look into that.
- dijereedan 6y agoWhat about genetic optimization?
- simonblanke 6y agoGradient-Free-Optimizers has a type of genetic algorithm: Evolution Strategy
- aldanor 6y agoLooks very nice! Two questions off top of my head: - Might be worth mentioning how Hyperactive compares to tons of other similar packages, like Hyperopt, Optunity and a ton of others? Also how your GFO package is different from optima, opytimizer, and many others as well. Having some benchmarks or performance stats (or even just listing functionality differences) would be very helpful to anyone who's been already using those. - One of the best universal 'works-out-of-the-box-most-of-time' global optimizers I've used recently is DLib's: http://blog.dlib.net/2017/12/a-global-optimization-algorithm-worth.html http://blog.dlib.net/2017/12/a-global-optimization-algorithm... - any chances for implementing something similar?
- simonblanke 6y agoTwo very interesting questions! I should work soon on a comparison of Hyperactive and GFO to other packages. If some important features are missing, maybe i could add them. I will also look into Dlib. If you like you can open an official issue in my repository. We could discuss why it is useful and if it should be implemented.
- batterylow 6y agoA book on Practical Evolutionary Algorithms with Python for anyone interested https://datacrayon.com/shop/product/practical-evolutionary-algorithms-book/ https://datacrayon.com/shop/product/practical-evolutionary-a...
- stilley2 6y agoCool! I'd considering adding CMA-ES [1], which as far as I know is the gold standard for derivative free optimization. 1. https://en.m.wikipedia.org/wiki/CMA-ES https://en.m.wikipedia.org/wiki/CMA-ES
- stilley2 6y agoAh nevermind I see this was addressed in another comment.
- MauranKilom 6y agoI'd recommend also implementing the DIRECT algorithm, which balances local and global search very well (but consequently will not refine as aggressively near the current [possibly only local] optimum as other algorithms): https://www.researchgate.net/profile/Donald-Jones-5/publication/249598200_The_DIRECT_global_optimization_algorithm/links/5ca2184f92851cf0aea5e3d5/The-DIRECT-global-optimization-algorithm.pdf?origin=publication_detail https://www.researchgate.net/profile/Donald-Jones-5/publicat... You probably also want to include some advantages/disadvantages of each algorithm. How robust against local minima is it? Up to how many dimensions does it work well? How is the convergence speed when started far from the optimum? Does it work well with few function evaluations? Etc.
- simonblanke 6y agoI will look into this algorithm. Thanks for the suggestion. I have some basic explanations of the optimization techniques and their parameters in a separate repository: https://github.com/SimonBlanke/optimization-tutorial https://github.com/SimonBlanke/optimization-tutorial But there is still a lot of work to be done.
- uyt 6y agoFor those who want to learn more, I really like the book "Algorithms for Optimization": https://algorithmsbook.com/optimization/#outline https://algorithmsbook.com/optimization/#outline It's a great intro because it covers a large breadth and gives you a sense of what class of techniques are useful for what (rather than just going super deep into one particular technique). They also have a github in julia notebooks implementing most of the ideas: https://github.com/sisl/algforopt-notebooks https://github.com/sisl/algforopt-notebooks
- yaroslavvb 6y agoSPSA seems to be missing. OpenAI's "evolutionary strategies" paper used a form of SPSA. https://en.wikipedia.org/wiki/Simultaneous_perturbation_stochastic_approximation https://en.wikipedia.org/wiki/Simultaneous_perturbation_stoc...
- freemint 6y agoIf you have an expensive but not high dimensional problem you might want to try https://github.com/DLR-SC/sqpdfo https://github.com/DLR-SC/sqpdfo . It is based on Krigging, SQP and also handles constraints.
- 5d749d7da7d5 6y agoThis looks super interesting, I have previously considered using the Bayesian Optimization[0] package for some work, but the ability to switch out the underlying algorithms is appealing. Perhaps a bit of a far out question - I would be interested in using this for optimizing real-world (ie slow, expensive, noisy) processes. A caveat with this is that the work is done in batches (eg N experiments at a time). Is there a mechanism by which I could feed in my results from previous rounds and have the algorithm suggest the next N configurations that are sufficiently uncorrelated to explore promising space without bunching on top of each-other? My immediate read is that I could use the package to pick the next optimal point, but would then have to lean on a random search for the remainder of the batch? 0: https://github.com/fmfn/BayesianOptimization https://github.com/fmfn/BayesianOptimization
- simonblanke 6y agoYes it is quite easy to switch algorithms via the "gpr" parameter. You just have to write a wrapper class. I am currently working on a repository that discusses how to do that in detail: https://github.com/SimonBlanke/surrogate-models https://github.com/SimonBlanke/surrogate-models I will upload some examples (GPy and Gpflow) within the next 24 hours. I think those wrapper-classes will already answer some of your questions. If you have additional or unanswered questions you can open an issue in the Grad-Free-Opt repository.
- person_of_color 6y agoDoes this include Hill Climbing ?
- simonblanke 6y agoYes Hill Climbing + some of its variants are featured in this package.