Adaptive Partitioning Schemes for Optimistic Optimization

Applications such as engineering design often require us to optimize a black-box function, i.e., a system whose inner processing is not analytically known and whose gradients are not available. Practitioners often have a fixed budget for the number of function evaluations and the performance of an optimization algorithm is measured by its simple regret. In this paper, we study the class of ``Optimistic Optimization'' algorithms for black-box optimization that use a partitioning scheme for the domain. We develop algorithms that learn a good partitioning scheme and use flexible surrogate models such as neural networks in the optimization procedure. For multi-index functions on an $m$-dimensional subspace within $d$ dimensions, our algorithm attains $\tilde{O}(n^{-\beta / d})$ regret, where $\beta = 1 + \frac{d-m}{2m-1}$, as opposed to $\tilde{O}(n^{-1/d})$ for SequOOL, a state-of-the-art optimistic optimization algorithm. Our approach is competitive across a wide range of numerical benchmarks. Additionally, we introduce weight quantization in a large language model as a novel task for black-box optimization. Our approach improves the quality of Activation-aware Weight Quantization (AWQ) of the OPT-1.3B model, achieving an approximate 10\% improvement in performance relative to the best possible unquantized model.

Engineers often want to find the best solution to complex problems that take time to experiment with, like finding new drug molecules or designing aircraft wings. This becomes extremely challenging when many factors are involved, making traditional search methods slow and inefficient. This paper develops a new approach that uses neural networks to identify which factors matter most, then focuses the search on those key areas rather than exploring everything blindly. When tested on standard problems and applied to making AI language models more efficient, this method found better solutions faster than existing techniques. This research matters because it could help solve complex optimization problems more quickly in various fields, from engineering design to making AI systems run on everyday devices.