Search faster by learning where the function actually varies (ICML 2025)
Many black-box functions with dozens of inputs really depend on only a few combinations of them. Optimistic optimization algorithms such as SequOOL split the search space into cells and refine the promising ones, but their splits are fixed in advance, so they pay for every dimension.
This project learns the low-dimensional subspace from a small number of evaluations, using a neural network surrogate, and then partitions along it. For functions that vary in an $m$-dimensional subspace of $d$ dimensions, the regret improves from $\tilde{O}(n^{-1/d})$ to $\tilde{O}(n^{-\beta/d})$ with $\beta = 1 + \frac{d-m}{2m-1}$. The method is competitive on standard benchmarks, and the paper introduces LLM weight quantization as a new black-box optimization task.
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 \tildeO(n^-β/ d) regret, where β= 1 + \fracd-m2m-1, as opposed to \tildeO(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.
@inproceedings{sunkara2025adaptive,title={Adaptive Partitioning Schemes for Optimistic Optimization},author={Sunkara, Raja and Tripathy, Ardhendu},booktitle={Proceedings of the 42nd International Conference on Machine Learning},series={Proceedings of Machine Learning Research},volume={267},pages={58029--58064},year={2025},publisher={PMLR},}
