Spring 2026

Grid search and random search are widely used techniques for optimizing black-box functions when gradient information is unavailable. In these methods, a finite set of candidate points is evaluated, and the best-performing one is selected. We propose a simple and computationally inexpensive refinement of this paradigm: instead of selecting a single best point, we form a weighted average of the evaluated points, where the weights are chosen using an importance sampling scheme inspired by the Laplace principle. This scheme can be implemented as a post-processing step on top of random search, with no additional function evaluations. We also propose an iterative variant in which the sampling distributions are adaptively chosen to generate new candidate points around the previous estimate, in the spirit of Evolution Strategy (ES) methods. In a general non-convex setting, we show that after n evaluations, the error of the proposed methods is of smaller order than n^{-2/(d+2)}. This compares favorably with the n^{-1/d} rates of random search or grid search as soon as d > 2.