Scaling of Probability-Based Optimization Algorithms

Population-based Incremental Learning is shown require very sen(cid:173) sitive scaling of its learning rate. The learning rate must scale with the system size in a problem-dependent way. This is shown in two problems: the needle-in-a haystack, in which the learning rate must vanish exponentially in the system size, and in a smooth function in which the learning rate must vanish like the square root of the system size. Two methods are proposed for removing this sensitiv(cid:173) ity. A learning dynamics which obeys detailed balance is shown to give consistent performance over the entire range of learning rates.