Slashdot Mirror
'Shrinking Bull's-eye' Algorithm Speeds Up Complex Modeling From Days To Hours (mit.edu)
rtoz sends word of the discovery of a new algorithm that dramatically reduces the computation time for complex processes. Scientists from MIT say it conceptually resembles a shrinking bull's eye, incrementally narrowing down on its target. "With this method, the researchers were able to arrive at the same answer as a classic computational approaches, but 200 times faster." Their full academic paper is available at the arXiv. "The algorithm can be applied to any complex model to quickly determine the probability distribution, or the most likely values, for an unknown parameter. Like the MCMC analysis, the algorithm runs a given model with various inputs — though sparingly, as this process can be quite time-consuming. To speed the process up, the algorithm also uses relevant data to help narrow in on approximate values for unknown parameters."
It looks to me that the new algorithm offers no real speed advantage over gaussian process optimization. Rather, by making similar local approximations it gains some convergence proofs. Those are nice and all, but not often relevant to real-world applications.
Not really, Zeno's paradox is about an infinite sum giving a finite result.
The technique in the article look more like a typical monte-carlo method (that is generating a lot of random values to find a result) combined with some localized search around local maximums. As such that does not seem to be a new idea. I haven't read the whole paper yet but the innovation seems to be in the fact that they managed to apply this idea to a new class of problems.
Indeed, it looks much like this. I happend to have a dozen EDA papers from the past couple decades open on my desktop at this moment! The foremost of the three hard problems in estimation of distribution is how one describes a probability distribution over high dimensional space in a compact low dimensional way. An efficient, if naive, way to do this is just fit the distribution to a function like a Gaussian and then just change the axes and width of the gaussian to evolve it. one then can easily sample and update this gaussian process to narrow down on the parameter guesses. This may be what they "bullseye" approach is doing from the description. Another more general approach I just happened to be re-reading today is the Probability collective which sort of divides the high dimensional space into a low dimensional product distribution. This can handle non-unimodal surfaces and by adapting the basis for the product space coordiantes adapt itself to the local topology. there's a lot of papers on this including this one: http://www.worldscientific.com... (perhaps not the best starting place but I had the link handy!).
The other two hard problems are how one optimally re-uses old data which was taken in what is now the low probality region. one has to down weight it wrt to fresher samples but how is unclear. Finally there's the annealing schedule which reflects the trade between exploration of the surface versus exploitation of the available data. anneal quickly and you converge to local minimum and miss the global minimum. Usually these are arbitrary. But Probability collectives has some clever techniques to make those decisions more principled. In general setting the annealing rate by cross validation is good way to decide if you should anneal faster or slower.