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 O~(n−β/d) regret, where β=1+2m−1d−m, as opposed to O~(n−1/d) for SequOOL, a state-of-the-art optimistic optimization algorithm. We use our approach to improve the quality of Activation-aware Weight Quantization (AWQ) of the OPT-1.3B model, achieving ∼10% improvement in performance relative to the best possible unquantized model.
Figures & tables
SOO
SequOOL
Our Method
η=0
ρn
ρΩ~(n)
ρβΩ~(n)
η>0
O~(n−1/η)
O~(n−1/η)
O~(n−β/η)
Table 1: Regret bounds on a budget of n evaluations for a m -dimensional multi-index function in d dimensions. β=1+2m−1d−m and ρ,η are parameters for the default partitioning scheme.
Figure 1: First four depths of the default partitioning P on [−1,1]2
Figure 2: Illustration of Lemma 4.5 for d=2,m=1 , showing the true subspace A and the estimated subspace A^ used in defining the expansion factor.
Figure 3: Regret Plots: Algorithm 1 (SequOOL on A^ ) uses 650 additional samples to learn the subspace. Regret is plotted for 100 equally spaced budget values between 1 and 2000. For the randomized algorithms, we took 10 trials and plotted the median curve (thick line) and 0 and 95 percentile curves. Random Search is run on A^ .
Algorithm
Compute
WikiText-2
Calibration
Time
PPL
-Set PPL
Grid Search
≈ 9 hours
16.92
14.62
SequOOL
≈ 10 hours
16.83
14.28
Algorithm 1
≈ 10 hours
16.96
14.42
Algorithm 2
≈ 12 hours
16.68
14.29
Table 2: LLM Quantization Experiment Results
Figure 4: Optimal splitting ratio between the first and second directions. Green curve is obtained using the strategy in Definition 10.1
Figure 5: Regret at n=300 for SequOOL on A with varying θ .
Figure 6: Caption
Figure 7: Regret Plots: Legend for the plots are arranged in the order of their performance. Algorithm 1 (SequOOL on A^ ) uses 100 additional samples to learn the subspace through the Fornasier et al. (2012) approach. Our Algorithm, SOO, RESOO, SequOOL are budget algorithms, so we run these algorithms using 100 equally spaced budget values between 1 and 2000 and plot the regret at the end of each run. For the randomized algorithms, we took 10 trials and plotted the median curve (thick line) and 0 and 95 percentile curves. Random Search is run on A^ .
Bayesian optimization is a sequential method for minimizing objective functions that are expensive to evaluate and about which few assumptions can be made. By using all gathered data to train a Gaussian process model for the function and adaptively employing a mixture of global exploration and local exploitation, this method has been used for optimization in many fields including machine learning, automotive engineering and reinforcement learning. However, the standard method suffers from two problems: 1) with cubic computational complexity in the training-set size it eventually becomes computationally infeasible to train the model, and 2) globally modeling the objective function is not necessarily optimal given the local nature of minimization. Using flexible and recursive binary partitioning of the search space, we adapt both the modeling and acquisitive aspects of standard Bayesian optimization to work harmoniously with the partitioning scheme, thereby ameliorating both standard shortcomings. We compare our method against a commonly used Bayesian optimization library on seven challenging test functions, ranging in dimensionality from 6 to 124, and show that our method achieves superior optimization performance in all tests. In addition our method has linear computational complexity.
Jesse Schneider, William J. Welch
Department of Statistics, University of British Columbia, Vancouver, BC V6T 1Z4, Canada
We study the problem of black-box optimization of a function f of any dimension, given function evaluations perturbed by noise. The function is assumed to be locally smooth around one of its global optima, but this smoothness is unknown. Our contribution is an adaptive optimization algorithm, POO or parallel optimistic optimization, that is able to deal with this setting. POO performs almost as well as the best known algorithms requiring the knowledge of the smoothness. Furthermore, POO works for a larger class of functions than what was previously considered, especially for functions that are difficult to optimize, in a very precise sense. We provide a finite-time analysis of POO's performance, which shows that its error after n evaluations is at most a factor of sqrt(ln n) away from the error of the best known optimization algorithms using the knowledge of the smoothness.
Jean-Bastien Grill, Michal Valko, Rémi Munos
SequeL team, INRIA Lille - Nord Europe, France · Google DeepMind, UK∗
We consider function optimization as a sequential decision making problem under budget constraint. This constraint limits the number of objective function evaluations allowed during the optimization. We consider an algorithm inspired by a continuous version of a multi-armed bandit problem which attacks this optimization problem by solving the tradeoff between exploration (initial quasi-uniform search of the domain) and exploitation (local optimization around the potentially global maxima). We introduce the so-called Simultaneous Optimistic Optimization (SOO), a deterministic algorithm that works by domain partitioning. The benefit of such approach are the guarantees on the returned solution and the numerical efficiency of the algorithm. We present this machine learning approach to optimization, and provide the empirical assessment of SOO on the CEC'2014 competition on single objective real-parameter numerical optimization test-suite.
Philippe Preux, Rémi Munos, Michal Valko
Université de Lille, LIFL (UMR 8022 CNRS), and INRIA, France · INRIA, and LIFL, Lille, France