Adaptive Partitioning Schemes for Optimistic Optimization

Raja Sunkara; Ardhendu Tripathy

stat.MLOct 2, 2026

Adaptive Partitioning Schemes for Optimistic Optimization

Authors: Raja Sunkara, Ardhendu Tripathy

Organizations: Missouri University of Science & Technology, Rolla MO, US · OpsCanvas, Alexandria VA, US.

Abstract

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^{-β/ d})$ regret, where $β= 1 + \frac{d-m}{2m-1}$ , as opposed to $\tilde{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 $\sim10\%$ improvement in performance relative to the best possible unquantized model.

Figures & tables

	SOO	SequOOL	Our Method
$\eta=0$	$\rho^{\sqrt{n}}$	$\rho^{\tilde{\Omega}(n)}$	$\rho^{\beta\tilde{\Omega}(n)}$
$\eta>0$	$\tilde{O}(n^{-1/\eta})$	$\tilde{O}(n^{-1/\eta})$	$\tilde{O}(n^{-\beta/\eta})$

Table 1: Regret bounds on a budget of

n

evaluations for a

m

-dimensional multi-index function in

d

dimensions.

\beta=1+\frac{d-m}{2m-1}

and

\rho,\eta

are parameters for the default partitioning scheme.

Figure 1: First four depths of the default partitioning

\mathcal{P}

[-1,1]^{2}

Figure 2: Illustration of Lemma 4.5 for $d=2,m=1$ , showing the true subspace $\boldsymbol{\mathbf{A}}$ and the estimated subspace $\hat{\boldsymbol{\mathbf{A}}}$ used in defining the expansion factor.

Figure 3: Regret Plots: Algorithm 1 (SequOOL on $\hat{\mathcal{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 $\hat{\mathcal{A}}$ .

Algorithm	Compute	WikiText-2	Calibration
	Time	PPL	-Set PPL
Grid Search	$\approx$ 9 hours	16.92	14.62
SequOOL	$\approx$ 10 hours	16.83	14.28
Algorithm 1	$\approx$ 10 hours	16.96	14.42
Algorithm 2	$\approx$ 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 $\boldsymbol{\mathbf{A}}$ with varying $\theta$ .

Figure 7: Regret Plots: Legend for the plots are arranged in the order of their performance. Algorithm 1 (SequOOL on $\hat{\mathcal{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 $\hat{\mathcal{A}}$ .

Black-Box Optimization

Black-box optimization finds high-quality solutions when objectives can only be queried, not directly analyzed or differentiated.

See all 176 papers

Bayesian Optimization in Linear Time
Apr 30, 2026Jesse Schneider, William J. WelchBayesian Optimization Black-Box Optimization
Department of Statistics, University of British Columbia, Vancouver, BC V6T 1Z4, Canada
Black-box optimization of noisy functions with unknown smoothness
May 4, 2026Jean-Bastien Grill, Michal Valko, Rémi MunosBlack-Box Optimization Zeroth-Order Optimization
SequeL team, INRIA Lille - Nord Europe, France · Google DeepMind, UK∗
Bandits attack function optimization
May 5, 2026Philippe Preux, Rémi Munos, Michal ValkoBlack-Box Optimization Global Optimization
Université de Lille, LIFL (UMR 8022 CNRS), and INRIA, France · INRIA, and LIFL, Lille, France

Apr 30, 2026J/K move · Enter open · S save

Bayesian Optimization in Linear Time

Jesse Schneider, William J. Welch

Department of Statistics, University of British Columbia, Vancouver, BC V6T 1Z4, Canada

Bayesian Optimization Black-Box Optimization

Open paper AskPDF arXiv

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

124

, and show that our method achieves superior optimization performance in all tests. In addition our method has linear computational complexity.

Abstract

Black-Box Optimization

Explore similar work

Bayesian Optimization in Linear Time

Black-box optimization of noisy functions with unknown smoothness

Bandits attack function optimization