Probability Collectives in Optimization

This article concerns “blackbox optimization” algorithms in which one iterates the following procedure: Choose a value x 2 X, getting statistical information about an associated value G(x), then use the set of all pairs f(x;G(x))g found so far to choose a next x value at which to sample G, the goal being to find x’s with as small G(x) as possible, and to do so as fast as possible. Examples of conventional blackbox optimization algorithms are genetic algorithms, simulated annealing, etc. These conventional algorithms work directly with values x, stochastically mapping the set f(x;G(x))g to the next x. The distribution over new x’s that gets sampled is never explicitly optimized. In contrast, in the Probability Collectives (PC) approach, one explicitly uses the set f(x;G(x))g to optimize the probability distribution over x that will be sampled. This article reviews some of the work that has been done on Probability Collectives, in particular presenting some of the many experiments that have demonstrated its power.