Derivative free optimization via repeated classification
This provides an efficient, tuning-free method for derivative-free optimization in applications like DNA binding and airfoil design, though it appears incremental as it builds on existing classification and active learning concepts.
The paper tackles the problem of derivative-free optimization by using classifiers to identify sublevel sets, achieving linear convergence rates with sufficiently accurate classifiers. The resulting algorithm outperforms other approaches on simulations, benchmarks, DNA binding optimization, and airfoil design problems in batched query settings.
We develop an algorithm for minimizing a function using $n$ batched function value measurements at each of $T$ rounds by using classifiers to identify a function's sublevel set. We show that sufficiently accurate classifiers can achieve linear convergence rates, and show that the convergence rate is tied to the difficulty of active learning sublevel sets. Further, we show that the bootstrap is a computationally efficient approximation to the necessary classification scheme. The end result is a computationally efficient derivative-free algorithm requiring no tuning that consistently outperforms other approaches on simulations, standard benchmarks, real-world DNA binding optimization, and airfoil design problems whenever batched function queries are natural.