3 ms·
Hi there, You're right that it's tricky to make a direct comparison between different shaped optimization domains, however in the comparison animation each alg
by chroem- 9y ago
Hi there,
You're right that it's tricky to make a direct comparison between different shaped optimization domains, however in the comparison animation each algorithm was given an optimization domain of equal area. For comparisons in higher dimensions it is up to the user to specify optimization domains with equal content.
Simple's runtime performance is not affected by the size of the optimization domain, however any global optimization algorithm will necessarily need to make more samples to chraracterize a higher dimensional space because these spaces inherently have more content to explore. Essentially the runtime performance of the algorithm and its sample-efficiency are two orthogonal concepts. Simple promises to be at least as sample-efficient as Bayesian Optimization while offering significantly lower computational overhead. Its main selling point isn't improved sample efficiency so much as better performance.
Does that answer your questions?
EDIT: Regarding the appropriate problem dimensionality, that will tend to depend quite a bit on the specific optimization problem. Simple is a global optimizer, so for extremely dimensional problems like training a deep neural net it would not be appropriate because the optimization domain would be too massive. The algorithm needs more testing, but as a rule of thumb I would say that anything under 500 dimensions is feasible.
- Straw 9y agoI think you may underestimate the scaling of global optimization with dimension. You split each simplex into n+1 smaller ones in n dimensions, so even in 99 dimensions, the number of areas to consider grows as 100^k! After only a few subdivisions, the regions may be still pretty large, but suddenly you're dealing with thousands or millions of reasonable candidates. If your optimization problem is particularly easy, you might manage it, but in tricky cases it just cannot scale. This isn't a flaw in your algorithm - global optimization of non 'nice' functions in high dimensions is essentially impossible for the same reasons. Luckily, turns out that in a lot of cases you don't need a global maximum, only something good enough, so the NN folks aren't bothered.