'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."

Comments

Estimation of distribution algorithm

[goombah99]

Uh isn't this a toy version of the entire field Estimation of Distribution Algorithms for parameter optimization??? Anyone want to point out what is new here since the MIT article sure didn't point it out.

Re:Estimation of distribution algorithm

[Anonymous Coward]

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.

Re:Estimation of distribution algorithm

[notea42]

Yep - it looks like they rediscovered known methods for optimization using a series of cheap approximations of the black-box. You find the optimal solution of the approximation and use that to choose one or more points to evaluate on the original black-box. Then you update your approximation with the results and repeat. I was doing this in college back in 1999. I wrote to generate pseudo-random functions to test on, and we used the same class of functions as approximations for the harder, more expensive problem.

Re:Estimation of distribution algorithm

[notea42]

Found the other relevant paper - "Model-assisted pattern search methods for optimizing expensive computer simulations" by Seifert, Torczon, and Trosset at The College of William and Mary in VA

Somewhat hyped

[GlobalEcho]

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.

Looks familiar ...

[leftover]

Is this not hill-climbing on an assumed-flat-ish response surface? There is history and a whole forest of approaches using approximation when the "cost" function is expensive to evaluate. Solving a honking big set of PDEs certainly qualifies for that.

A big part of the history is work to predict whether the degree of assumed flatness is not in conflict with reality. That in itself can become computationally expensive.

Fun stuff though!

IANACS

[Anonymous Coward]

So I'm a lay-idiot, but whats to stop this getting stuck on a local maxima / minima for a given parameter if it's not doing a comprehensive evaluation?

Re:This sounds familiar...

[geantvert]

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.

Huh

[ThatsNotPudding]

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.

Huh. You think they would have realized that more quickly.

Enigma / bomba

[ai4px]

Isn't this shrinking bullseye the same strategy that was used by Turning to throw out all the impossible solutions to the enigma machine? This left the team with many fewer possible solutions to try by brute force.