In bagging [Bre94a] one uses bootstrap replicates of the training set [Efr79, ET93] to try to improve a learning algorithm's performance. The computational requirements for estimating the resultant generalization error on a test set by means of cross-validation are often prohibitive; for...

We explore the 2-armed bandit with Gaussian payoffs as a theoretical model for optimization. We formulate the problem from a Bayesian perspective, and provide the optimal strategy for both 1 and 2 pulls. We present regions of parameter space where a greedy strategy is provably optimal. We also...

We show that all algorithms that search for an extremum of a cost function perform exactly the same, when averaged over all possible cost functions. In particular, if algorithm A outperforms algorithm B on some cost functions, then loosely speaking there must exist exactly as many other...

For systems usually characterized as complex/living/intelligent, the spatio-temporal patterns exhibited on different scales differ markedly from one another. (E.g., the biomass distribution of a human body looks very different depending on the spatial scale at which one examines that biomass.)...

Optimization of systems with many conflicting constraints arises in numerous settings. Common optimization procedures seek to improve performance of the system as a whole. We show that coevolutionary problem solving, in which a system is partitioned into subsystems each of which selfishly...

A new approach to drug discovery is based on the generation of high diversity libraries of DNA, RNA, peptides or small molecules. Search of such libraries for useful molecules is an optimization problem of high-dimensional molecular fitness landscapes. We utilize a spin-glass-like model, the NK...

Technological change at the firm-level has commonly been modeled as random sampling from a fixed distribution of possibilities. Such models typically ignore empirically important aspects of the firm's search process, namely the related observations that a firm's current technology constrains...

Technological change at the firm level has commonly been modeled as random sampling from a fixed distribution o f possibilities. Such models, however, typically ignore empirically important aspects of the firm's search process, notably the observation that the present state of the firm guides...

We demonstrate the existence of a phase transition in combinatorial optimization problems. For many of these problems, as local search algorithms are parallelized, the quality of solutions first improves and then sharply degrades to no better than random search. This transition can be...

This paper proves that one can not build a computer which can, for any physical system, take the specification of that system's state as input and then correctly predict its future state before that state actually occurs. Loosely speaking, this means that one can not build a physical computer...