Global Optimization with Parametric Function Approximation
This addresses the problem of efficient global optimization for applications such as hyper-parameter tuning and material design, offering a novel parametric approach that improves upon incremental advances in non-parametric methods.
The paper tackles global optimization with noisy zeroth-order oracles, proposing GO-UCB, a new algorithm that uses parametric function approximation like neural networks to overcome the curse of dimensionality in existing non-parametric methods, achieving a cumulative regret of Õ(√T) under certain assumptions and outperforming Bayesian optimization in experiments.
We consider the problem of global optimization with noisy zeroth order oracles - a well-motivated problem useful for various applications ranging from hyper-parameter tuning for deep learning to new material design. Existing work relies on Gaussian processes or other non-parametric family, which suffers from the curse of dimensionality. In this paper, we propose a new algorithm GO-UCB that leverages a parametric family of functions (e.g., neural networks) instead. Under a realizable assumption and a few other mild geometric conditions, we show that GO-UCB achieves a cumulative regret of Õ$(\sqrt{T})$ where $T$ is the time horizon. At the core of GO-UCB is a carefully designed uncertainty set over parameters based on gradients that allows optimistic exploration. Synthetic and real-world experiments illustrate GO-UCB works better than popular Bayesian optimization approaches, even if the model is misspecified.